LeetCode 148: Sort List - 鏈表歸並排序 O(n log n) 常數空間

問題描述

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

歸並排序適用鏈表

單鏈表不支持隨機訪問，快排不宜；歸並排序只需順序訪問，天然適合。
步驟：
1. 快慢指針找中點斷開。
2. 遞歸排序左右兩半。
3. 合併兩有序鏈表（復用 Merge Two Sorted Lists 邏輯）。

代碼

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->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(0), *p = &dummy;
    while (a && b) {
        if (a->val < b->val) p->next = a, a = a->next;
        else p->next = b, b = b->next;
        p = p->next;
    }
    p->next = a ? a : b;
    return dummy.next;
}