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 };
