Sort a linked list using insertion sort.
链表的插入排序实现原理很简单，就是一个元素一个元素的从原链表中取出来，然后按顺序插入到新链表中，时间复杂度为O(n2)，是一种效率并不是很高的算法，但是空间复杂度为O(1)，以高时间复杂度换取了低空间复杂度。代码如下：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *insertionSortList(ListNode *head) { ListNode *res = new ListNode(-1); ListNode *cur = res; while (head) { ListNode *next = head->next; cur = res; while (cur->next && cur->next->val <= head->val) { cur = cur->next; } head->next = cur->next; cur->next = head; head = next; } return res->next; } };
本文转自博客园Grandyang的博客，原文链接：链表插入排序[LeetCode] Insertion Sort List ，如需转载请自行联系原博主。
