LeetCode Insertion Sort List：鏈表插入排序實現

問題描述

對單鏈表進行插入排序，返回排序後頭節點。要求原地排序。

算法思路

維護一個已排序部分鏈表（虛擬頭節點 dummy），遍歷原鏈表，將每個節點摘下，在已排序部分找到插入位置並插入。

關鍵步驟

1. 創建 dummy，dummy->next = head
2. sortedTail 指向已排序部分尾部（初始為 head）
3. 遍歷 cur = sortedTail->next（待插入節點）
4. 若 cur->val >= sortedTail->val，直接擴展已排序部分
5. 否則從 dummy 開始找第一個大於 cur->val 的節點 pre，插入到 pre 後
6. 注意斷開 cur 與原後繼的連接，避免環

完整代碼

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode dummy(0);
        dummy.next = head;
        ListNode *sortedTail = head;
        ListNode *cur = head->next;
        sortedTail->next = nullptr; // 斷開，已排序部分只有 head
        while (cur) {
            ListNode *next = cur->next;
            cur->next = nullptr;
            if (cur->val >= sortedTail->val) {
                sortedTail->next = cur;
                sortedTail = cur;
            } else {
                ListNode *pre = &dummy;
                while (pre->next && pre->next->val < cur->val) pre = pre->next;
                cur->next = pre->next;
                pre->next = cur;
            }
            cur = next;
        }
        return dummy.next;
    }
};

複雜度

• 時間：O(n²)，最壞情況逆序
• 空間：O(1)，原地排序

易錯點

1. 摘下節點時必須保存 next 並置 cur->next=nullptr
2. 插入位置查找從 dummy 開始，而非 head，否則無法處理插到頭部的情況
3. sortedTail 僅在尾插時更新，中間插入不動

鏈表插入排序雖非最優（歸併排序 O(n log n)），但思路直觀，是理解鏈表指針操作的優秀練習。