LeetCode 148 排序鏈表：歸並排序 O(n log n) 完美實現

題目要求

在 O(n log n) 時間、O(1) 空間（遞歸棧除外）內對單鏈表排序。顯然需用歸並排序（穩定、鏈表天然適合）或快速排序（鏈表分區困難）。本文採用自頂向下歸並排序。

核心算法流程

1. 分割：快慢指針找中點，斷開成兩半
2. 遞歸排序：分別排序左右半部分鏈表
3. 合併：雙指針合併兩個有序鏈表

關鍵技術點詳解

1. 快慢指針找中點（前中點）

ListNode* getMid(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) { // 關鍵條件
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow; // 偶數長度返回前中點
}

• fast->next && fast->next->next 確保 slow 停在前中點
• 長度 4：索引 0,1,2,3 → slow 停在 1（前中點）
• 斷開：mid->next = nullptr 分成兩獨立鏈表

2. 有序鏈表合併（哨兵節點簡化邊界）

ListNode* merge(ListNode* a, ListNode* b) {
    ListNode dummy(-1), *tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) tail->next = a, a = a->next;
        else tail->next = b, b = b->next;
        tail = tail->next;
    }
    tail->next = a ? a : b; // 掛上剩余部分
    return dummy.next;
}

• 哨兵節點 dummy 避免頭節點特判
• 尾指針 tail 追蹤合併尾部，O(1) 接駁
• 原地合併，無額外節點分配

完整遞歸實現

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head; // 基礎情況
        
        ListNode* mid = getMid(head);
        ListNode* right = mid->next;
        mid->next = nullptr; // 斷開
        
        return merge(sortList(head), sortList(right));
    }
    
private:
    ListNode* getMid(ListNode* head) { /* 同上 */ }
    ListNode* merge(ListNode* a, ListNode* b) { /* 同上 */ }
};

複雜度分析

進階：自底向上迭代歸並（O(1) 空間）

LeetCode 進階要求 O(1) 空間，需用迭代法：

1. 先算鏈表長度 len
2. 子鏈表長度 step = 1, 2, 4... < len
3. 每輪按 step 切分、兩兩合併、重組
4. 虛擬頭節點統一處理頭部變化

代碼較長但邏輯固定，是鏈表排序「終極模板」。

常見錯誤與調試

1. 找中點條件錯：用 fast->next 導致慢指針停在後中點，分割不均衡
2. 忘記斷開：mid->next = nullptr 缺失導致環或合併錯誤
3. 合併邊界漏判：剩余鏈表未掛載，丟失節點
4. 遞歸基礎情況漏判：!head || !head->next 缺一不可

總結

LeetCode 148 是鏈表歸並排序的標準考題。掌握「快慢指針分割 + 哨兵節點合併 + 遞歸/迭代框架」三大核心模組，即可靈活應對鏈表排序、求逆序對、合併 K 個鏈表等變體。遞歸版代碼簡潔易懂，面試首選；迭代版空間優化，工程實戰首選。

1. 上一篇文章： C++ Primer 學習筆記 69：面向對象編程——繼承情況下的類作用域
2. 下一篇文章： HDU 1269 迷宮城堡：強連通分量與 Tarjan 算法解析

C++ 入門

從尾到頭打印鏈表：棧與遞歸兩種實現對比

從尾到頭打印鏈表：棧與遞歸兩種實現對比 題目 輸入鏈表頭節點

POJ 2352 Stars：樹狀數組統計二維偏序級數

問題轉化 給定 n ≤ 15,000 個星星座標 (x,y)

仿《雷霆戰機》飛行射擊手遊開發（一）：專案總覽與架構設計

仿《雷霆戰機》飛行射擊手遊開發（一）：專案總覽與架構設計 本

C++ 入門筆記：字串處理與輸出格式化

C++ 入門筆記：字串處理與輸出格式化 記錄 C++ 字串學