本文共 1530 字，大约阅读时间需要 5 分钟。
Well, life gets difficult pretty soon whenever the same operation on array is transferred to linked list.
First, a quick recap of insertion sort:
Start from the second element (simply a[1] in array and the annoying head -> next -> val in linked list), each time when we see a node with val smaller than its previous node, we scan from the head and find the position that the current node should be inserted. Since a node may be inserted before head, we create a new_head that points to head. The insertion operation, however, is a little easier for linked list.
Now comes the code:
1 class Solution { 2 public: 3 ListNode* insertionSortList(ListNode* head) { 4 ListNode* new_head = new ListNode(0); 5 new_head -> next = head; 6 ListNode* pre = new_head; 7 ListNode* cur = head; 8 while (cur) { 9 if (cur -> next && cur -> next -> val < cur -> val) {10 while (pre -> next && pre -> next -> val < cur -> next -> val)11 pre = pre -> next;12 /* Insert cur -> next after pre.*/13 ListNode* temp = pre -> next;14 pre -> next = cur -> next;15 cur -> next = cur -> next -> next;16 pre -> next -> next = temp;17 /* Move pre back to new_head. */18 pre = new_head;19 }20 else cur = cur -> next;21 }22 ListNode* res = new_head -> next;23 delete new_head;24 return res;25 }26 };
转载地址：http://fmujl.baihongyu.com/