0023-Merge-k-Sorted-Lists

Problem Description

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Constraints:

• lists[i] is sorted in ascending order.

Solution

核心觀念是 0021-Merge-Two-Sorted-Lists 的直接推廣：答案的下一個節點，必定是 k 條串「當前 head」中最小的那個——每條串各自有序，一條串裡排在 head 後面的節點都不可能比自己的 head 更小，所以只有這 k 個是候選。

於是問題退化成一個很單純的資料結構問題：維護 k 個候選值，反覆取最小、然後補進一個新值。這正是 min-heap 的定義（方法一）。另一條路是換個切法——既然兩兩合併已經會寫，就想辦法讓每個節點被搬的次數變少，用分治把合併排成一棵樹（方法二）。兩者都是 O(N log k)，N 是總節點數。

lists = [ 1ₐ→ 4ₐ→ 5ₐ ,  1ᵦ→ 3ᵦ→ 4ᵦ ,  2ᵧ→ 6ᵧ ]        （下標標示節點來自哪一條串）

每一步只在「k 個當前 head」裡挑最小 —— 堆的大小恆 ≤ k，與 N 無關

   堆內容        取出          答案尾端            補回同一條串的下一個
  ──────────────────────────────────────────────────────────────────
   {1ₐ,1ᵦ,2ᵧ}     1ₐ    →     1ₐ                    push 4ₐ
   {1ᵦ,2ᵧ,4ₐ}     1ᵦ    →     1ₐ→1ᵦ                 push 3ᵦ
   {2ᵧ,3ᵦ,4ₐ}     2ᵧ    →     1ₐ→1ᵦ→2ᵧ              push 6ᵧ
   {3ᵦ,4ₐ,6ᵧ}     3ᵦ    →     1ₐ→1ᵦ→2ᵧ→3ᵦ           push 4ᵦ
   {4ₐ,4ᵦ,6ᵧ}     4ₐ    →     ⋯→4ₐ                  push 5ₐ
   {4ᵦ,5ₐ,6ᵧ}     4ᵦ    →     ⋯→4ₐ→4ᵦ               β 串已盡，不補
   {5ₐ,6ᵧ}        5ₐ    →     ⋯→5ₐ                  α 串已盡，不補
   {6ᵧ}           6ᵧ    →     ⋯→6ᵧ                  γ 串已盡，堆空 → 結束

方法一：min-heap（k 路合併）— O(N log k)／O(k)

把 k 條串的 head 全部丟進 min-heap，每次 pop 最小的接到答案尾端，再把「它的下一個節點」push 回去補位。堆裡永遠是「每條還沒走完的串各出一個代表」。

// Time: O(N log k)  N 個節點各 push/pop 一次，堆高恆為 log k
// Space: O(k)       堆裡每條串最多佔一格；答案只重接指標，不配置節點
class Solution {
 public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](const ListNode *a, const ListNode *b) {
      return a->val > b->val;  // min-heap
    };
    priority_queue<ListNode *, vector<ListNode *>, decltype(cmp)> pq(cmp);

    for (const auto &l : lists) {
      if (l) {
        pq.push(l);
      }
    }

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

方法二：分治兩兩合併 — O(N log k)／O(1)

不用堆也能到同樣的複雜度：反覆把 k 條串兩兩配對合併，每輪串數減半，log k 輪之後只剩一條。內層的合併子程序就是 0021-Merge-Two-Sorted-Lists 原封不動。

循序合併（O(kN)，錯誤示範）         分治合併（O(N log k)）

acc  = L1                          第 1 輪   L1 L2 L3 L4 L5 L6 L7 L8    8 條
acc += L2   → 掃過 2L                        └──┴──┴──┴──╯ 前半配後半    ← 全體節點被搬 1 次
acc += L3   → 掃過 3L              第 2 輪   M1 M2 M3 M4                 4 條
acc += L4   → 掃過 4L                        └──┴──╯                     ← 全體節點被搬 1 次
    ⋯                              第 3 輪   M1 M2                       2 條
acc += Lk   → 掃過 kL                        └──╯                        ← 全體節點被搬 1 次
                                   結果      M1                          1 條
總搬運 L(2+3+⋯+k) = O(kN)          共 log k 輪，總搬運 O(N log k)

// Time: O(N log k)  共 log k 輪，每輪所有節點合計被搬過一次
// Space: O(1)       就地覆寫 lists，迭代版連遞迴堆疊都不用
class Solution {
 public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return nullptr;
    int n = lists.size();
    while (n > 1) {
      int m = (n + 1) / 2;  // 本輪結束後剩下的串數（奇數時最中間那條輪空）
      for (int i = 0; i < n / 2; ++i) {
        lists[i] = merge2(lists[i], lists[i + m]);  // 頭尾配對，輪空的留在原位
      }
      n = m;
    }
    return lists[0];
  }

 private:
  ListNode* merge2(ListNode *a, ListNode *b) {
    ListNode dummy(0);
    ListNode *cur = &dummy;
    while (a && b) {
      if (a->val <= b->val) {
        cur->next = a;
        a = a->next;
      } else {
        cur->next = b;
        b = b->next;
      }
      cur = cur->next;
    }
    cur->next = a ? a : b;
    return dummy.next;
  }
};

Related Problems

• 0021-Merge-Two-Sorted-Lists — 本題 k = 2 的特例，方法二的 merge2 就是它原封不動
• 0148-Sort-List — 鏈結串列版 merge sort，同樣是分治＋兩兩合併，只是這題已經幫你切好了
• 0703-Kth-Largest-Element-in-a-Stream — heap 的基本操作練習，同樣靠「維護固定大小的候選集」
• 0347-Top-K-Frequent-Elements — heap 的另一種用法，維護大小為 k 的堆做 top-k 而非 k 路合併
• 0378-Kth-Smallest-Element-in-a-Sorted-Matrix — 每列當一條有序串，完全相同的「k 個指標 + min-heap」骨架
• 0632-Smallest-Range-Covering-Elements-from-K-Lists — 同骨架再加一個視窗最大值，是這題的直接進階版
• STL-Pitfalls — comparator 的嚴格弱序要求、priority_queue 的比較方向