147. Insertion Sort List

class Solution { public: void printList(ListNode * head){ ListNode * curr = head; while(curr) { cout << curr->val << ' '; curr = curr->next; } cout << endl; } ListNode* insertionSortList(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; auto dummy = new ListNode(0); // a placeholder to help insert before head. dummy->next = head; auto curr = head->next; auto prev = head; auto next = curr->next; while (curr != nullptr){ ListNode * insert = dummy; // find insert position: after this node while(insert != curr && insert->next->val < curr->val) insert = insert->next; // if insert is before prev, swap if (insert != prev){ curr->next = insert->next; insert->next = curr; prev->next = next; } // after swapping, or no need to swap, just update curr = dummy->next; prev = dummy; while(curr != next){ curr = curr->next; prev = prev->next; } // found original place. Now curr = original next if (curr != nullptr) next = curr->next; } return dummy->next; } };