LeetCode 147 Insertion Sort List：鏈表插入排序 O(n²) 時間 O(1) 空間

題目回顧

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

算法邏輯：維護已排序部分，逐個插入

• dummy 虛擬頭節點，值為 INT_MIN
• cur 遍歷原鏈表
• 對每個 cur，在已排序部分鏈表中找到插入位置 pos（最後一個 ≤ cur->val 的節點）
• 將 cur 插入 pos 之後

C++ 代碼

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode dummy(INT_MIN);
        ListNode* cur = head;
        while (cur) {
            ListNode* pos = findInsertPos(&dummy, cur->val);
            ListNode* tmp = cur->next; // 保存下一個待處理節點
            cur->next = pos->next;
            pos->next = cur;
            cur = tmp;
        }
        return dummy.next;
    }
    
private:
    ListNode* findInsertPos(ListNode* head, int x) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur && cur->val <= x) {
            pre = cur;
            cur = cur->next;
        }
        return pre; // 插在 pre 之後
    }
};

關鍵點

1. 虛擬頭節點：統一處理插入到頭部的情況
2. 保存 tmp：插入操作會斷開 cur->next，必須先保存
3. 查找插入位置：線性掃描已排序部分，找到最後一個 ≤ x 的節點

複雜度

• 時間：O(n²)，最壞情況逆序
• 空間：O(1)，只用常數額外指針

優化方向

若要求 O(n log n)，需用歸並排序（LeetCode 148），見下文。