LeetCode 23 Merge k Sorted Lists - 合併 K 個有序鏈表

題目翻譯

合併 k 個已排序的單鏈表，返回合併後的有序鏈表頭。分析時間空間複雜度。

解法一：分治法 (Divide & Conquer) — 推薦

將 k 個鏈表兩兩配對合併，類似歸併排序。遞歸將區間 [l, r] 分為 [l, mid] 和 [mid+1, r]，合併兩個有序鏈表（LeetCode 21）。

class Solution {
public:
    ListNode* mergeKLists(vector& lists) {
        if (lists.empty()) return nullptr;
        return merge(lists, 0, lists.size() - 1);
    }

    ListNode* merge(vector& lists, int l, int r) {
        if (l == r) return lists[l];
        int mid = (l + r) >> 1;
        ListNode* left = merge(lists, l, mid);
        ListNode* right = merge(lists, mid + 1, r);
        return mergeTwoLists(left, right);
    }

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val > l2->val) swap(l1, l2);
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    }
};

解法二：迭代式兩兩合併 (自底向上)

步長從 1 開始，每輪將相鄰兩個鏈表合併，步長翻倍，直到只剩一個鏈表。無遞歸棧，代碼稍長但同樣 O(N log k)。

ListNode* mergeKLists(vector& lists) {
    int n = lists.size();
    if (n == 0) return nullptr;
    int step = 1;
    while (step < n) {
        for (int i = 0; i + step < n; i += step * 2) {
            lists[i] = mergeTwoLists(lists[i], lists[i + step]);
        }
        step <<= 1;
    }
    return lists[0];
}

解法三：優先隊列 (最小堆)

將 k 個鏈表頭節點入堆，每次取最小節點輸出，並將其 next 入堆。時間 O(N log k)，空間 O(k)。

ListNode* mergeKLists(vector& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue, decltype(cmp)> pq(cmp);
    for (auto node : lists) if (node) pq.push(node);

    ListNode dummy(0), *tail = &dummy;
    while (!pq.empty()) {
        ListNode* cur = pq.top(); pq.pop();
        tail->next = cur;
        tail = cur;
        if (cur->next) pq.push(cur->next);
    }
    return dummy.next;
}

複雜度對比

其中 N 為所有節點總數。

總結

面試首選分治遞歸或最小堆。分治法複用 LeetCode 21 代碼，邏輯清晰；堆法思路直觀，適合講解「多路歸併」概念。注意處理空鏈表輸入。