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

題目要求

對單鏈表排序，時間 O(n log n)，空間 O(1) (不計遞歸棧)。

歸並排序適配鏈表

數組歸並需 O(n) 輔助空間，但鏈表**合併兩個有序鏈表只需 O(1) 空間** (僅調整指針)。
關鍵步驟：

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

代碼實現 (C++ / Java)

// C++
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        return mergeSort(head);
    }
private:
    ListNode* mergeSort(ListNode* head) {
        if (!head || !head->next) return head;
        // 快慢指針找中點
        ListNode *slow = head, *fast = head, *pre = nullptr;
        while (fast && fast->next) {
            fast = fast->next->next;
            pre = slow;
            slow = slow->next;
        }
        pre->next = nullptr; // 斷開
        ListNode* l1 = mergeSort(head);
        ListNode* l2 = mergeSort(slow);
        return merge(l1, l2);
    }
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(0), *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;
    }
};

// Java
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        return mergeSort(head);
    }
    private ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = head, pre = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        pre.next = null;
        ListNode l1 = mergeSort(head);
        ListNode l2 = mergeSort(slow);
        return merge(l1, l2);
    }
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
            else { tail.next = l2; l2 = l2.next; }
            tail = tail.next;
        }
        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

空間複雜度說明

• 遞歸棧深度 O(log n)，嚴格說不是 O(1)。
• 若要求嚴格 O(1) 空間，需改用**自底向上迭代歸並** (按長度 1,2,4... 合併)，避免遞歸。
• LeetCode 通常接受遞歸版本 (棧空間不計入)。

關鍵技巧

• `pre` 指針記錄 `slow` 前驅，用於斷開鏈表 (`pre->next = nullptr`)。
• 合併使用哨兵節點 `dummy` 簡化頭節點處理。
• 快慢指針初始 `fast = head` 而非 `head->next`，保證偶數長度時前半段 ≥ 後半段 (或任意一致即可)。