Sort a linked list using insertion sort.
思路就跟数组的插入排序思想一致，但是因为链表的只能从前往后遍历且无法随机访问，所以操作比较复杂，需要小心处理。
代码如下：
/** * 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* shead = new ListNode(0x80000000); ListNode* cur = head,*next; while(cur) { next = cur->next; ListNode* sCur = shead->next; ListNode* pre = shead; while(sCur) { if(cur->val > sCur->val) { pre = pre->next; sCur = sCur->next; } else break; } cur->next = pre->next; pre->next = cur; cur = next; } return shead->next; } };
结果发现性能不够理想，看看前面的更快的代码。发现其实不需要每次都进行从头判断进行插入，如果新插入的元素的值大于已经有序的元素中的最大值，直接进行下一个元素的判断即可，代码如下：
/** * 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* extra = new ListNode(0); extra->next = head; ListNode* p = extra; while(p->next){ auto cur = p->next; if(p == extra || cur->val >= p->val) { p = p->next; continue; } else { p->next = cur->next; } auto pre = extra; while(pre->next->val < cur->val) pre = pre->next; cur->next = pre->next; pre->next = cur; } return extra->next; } };
