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

問題描述

對單鏈表進行排序，要求 O(n log n) 時間、O(1) 額外空間。

歸並排序遞歸實現

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

代碼實現

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);
}

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;
}

複雜度分析

• 時間：O(n log n) — 每層合併 O(n)，遞歸深度 O(log n)。
• 空間：遞歸棧 O(log n)，若要求嚴格 O(1) 需改用迭代式自底向上歸並（按長度 1,2,4... 合併）。

插入排序版本（備選，O(n²)）

同 LeetCode 147，對近乎有序鏈表較快，但最壞 O(n²) 不符合題目要求。