LeetCode Merge k Sorted Lists — 分治歸並鏈表 O(N log k) 解法

問題描述

合併 k 條已排序鏈表為一條有序鏈表。分析複雜度。

分治歸並思路

兩兩合併：merge(lists, l, r) 遞歸合併區間 [l, r] 的鏈表，中點分治，最後歸並兩條有序鏈表。

參考代碼 (C++)

class Solution {
public:
    ListNode* merge(vector& lists, int l, int r) {
        if (l == r) return lists[l];
        int mid = (l + r) / 2;
        ListNode* p1 = merge(lists, l, mid);
        ListNode* p2 = merge(lists, mid+1, r);
        ListNode *head = nullptr, *p = nullptr;
        while (p1 && p2) {
            if (p1->val < p2->val) {
                if (p) p->next = p1; p = p1; p1 = p1->next;
            } else {
                if (p) p->next = p2; p = p2; p2 = p2->next;
            }
            if (!head) head = p;
        }
        if (p1) { if (p) p->next = p1; else { p = p1; head = p; } }
        if (p2) { if (p) p->next = p2; else { p = p2; head = p; } }
        return head;
    }

    ListNode* mergeKLists(vector& lists) {
        int sz = lists.size();
        if (sz == 0) return nullptr;
        if (sz == 1) return lists[0];
        return merge(lists, 0, sz-1);
    }
};

複雜度分析

• 設總節點數 N。每層合併處理所有節點一次，共 log k 層。
• 時間：O(N log k)。
• 空間：遞歸棧 O(log k)，原地合併 O(1) 額外空間。

替代方案對比

總結

分治歸並是合併 k 條有序鏈表的標準優雅解法，時間最優且代碼簡潔。優先隊列法同樣優秀，視語言習慣選擇。