LeetCode 148 Sort List：鏈表歸並排序 O(n log n) 時間 O(1) 空間

題目回顧

單鏈表排序，要求 O(n log n) 時間、O(1) 空間。

核心算法：自底向上歸並排序（或遞歸版）

遞歸版邏輯清晰，空間 O(log n) 遞歸棧，通常可接受。
關鍵步驟：

1. 找中點：快慢指針，slow 停在中點前驅
2. 斷開：slow->next = nullptr 分為左右兩部分鏈表
3. 遞歸排序：sortList(head), sortList(slow)
4. 合併：mergeTwoLists(l1, l2) 合併兩有序鏈表

C++ 代碼

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        // 快慢指針找中點
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        // 斷開
        ListNode* mid = slow->next;
        slow->next = nullptr;
        // 遞歸排序
        ListNode* l1 = sortList(head);
        ListNode* l2 = sortList(mid);
        // 合併
        return merge(l1, l2);
    }
    
private:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(-1);
        ListNode* tail = &dummy;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                tail->next = l1; l1 = l1->next;
            } else {
                tail->next = l2; l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

複雜度

• 時間：O(n log n)
• 空間：遞歸版 O(log n) 棧；迭代版（自底向上）可達 O(1)

總結

鏈表歸並排序是「分治 + 指針操作」的經典練習。關鍵點：快慢指針找中點、斷開遞歸、合併有序鏈表。面試必會。