LeetCode 147. Insertion Sort List [Medium] [C++] 解題筆記

 這題如題目本身，就是給你一個 Linked List 然後要求利用 insertion sort 的概念來進行排序。

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

想法:

    這題基本上在考察對 linked list 的操作熟不熟悉，主要就是直接照著 insertion sort 的演算法實作，

不過改成 linked list 在實作上有些小細節就要特別小心，例如每個 node 在 insert 前必須先把它的 next 指標

指到 nullptr，因為不處理的話有可能在排序完成後 linked list 中會存在 cycle，從而導致最後解構的時候重複訪問到

已經被釋放的指標造成 heap-use-after-free 的錯誤。

完整程式碼:

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* next = cur->next;
            ListNode* tmp = dummy.next;
            ListNode* pre = &dummy;
            // if we don't set this line, then there may have loop in list when we insert node. loop will cause heap-use-after-free when deconstruction
            // ex: 4->2->1->3 ==> 1->2->3-4 (and 4 will point to 2)
            cur->next = nullptr;
            while (tmp != cur) {
                if (tmp == nullptr) {
                    pre->next = cur;
                    break;
                }
                if (tmp->val >= cur->val) {
                    cur->next = tmp;
                    pre->next = cur;
                    break;
                }
                pre = tmp;
                tmp = tmp->next;
            }         
            cur = next;
        }
   
        return dummy.next;
    }
};