--- title: "23. Merge k Sorted Lists" url: "https://laigary.com/interview/coding/23-merge-k-sorted-lists" type: "note" section: "coding" date: "2023-01-29" updated: "2026-07-26" tags: ["Linked List", "Heap", "Classic"] --- # 23. Merge k Sorted Lists [23\. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/) 給 `k` 條已排序的鏈結串列，合併成一條。 ## 思路 這一題有多個不同的做法，我喜歡先從已經有的概念來出發。第一個概念是我們已經知道 [21. Merge Two Sorted Lists](/interview/coding/21-merge-two-sorted-lists) 的方法 —— 和 2 Sum 很像，我們如果知道了合併兩條，有沒有辦法延伸到合併 k 條？ ### 一、循序合併：一條一條疊上去 其實是可以的。第一個方法就是我們先從第一個和第二個 Linked List 合併，並存到結果上，再來合併結果跟第三個⋯⋯依此類推，一直到合併第 `k` 個。 這個做法一定寫得出來，但**效率不好**：累積的結果會越來越長，而每次合併都要把它整條再走一遍。第 `i` 次合併時結果已經有大約 `i * (N/k)` 個節點，加總起來是 $O(kN)$。 ### 二、兩兩分治：像合併排序那樣 其實這就很像是 [148. Sort List](/interview/coding/148-sort-list) —— 我們不用一個一個合併，我們可以**兩兩合併**就好。這樣合併的**輪數**就會從 `k` 次變成 $O(\log k)$ 次。 關鍵差別在於：循序合併時，同一批節點被重複走了 `k` 次；兩兩合併時，每個節點在每一「輪」只被走一次，而總共只有 $\log k$ 輪。 這裡要注意的就是數學的處理：如果說總共有偶數個 Linked List，每兩兩合併不會有太大的問題，可是如果是奇數個，那最後落單的要怎麼處理？或是偶數個 Linked List 合併之後變成奇數個了，那要怎麼處理？ 其實不用太擔心，因為奇數偶數會一直重複出現。主要的概念是第一次處理完後變成剩下 `k/2` 要處理，再處理一次後剩下 `k/4`，接著是 `k/8`⋯⋯直到結束。落單的那條**什麼都不用做**，下一輪它自然會找到配對。 可以用這個方式去看看變化： ```python if __name__ == '__main__': arr = [i for i in range(10)] interval = 1 while interval < len(arr): for i in range(0, len(arr) - interval, interval * 2): print(i, end=',') print() interval *= 2 ``` `range(0, amount - interval, interval * 2)` 裡的 `- interval` 就是在處理落單：如果 `i + interval` 會越界，那一輪就不碰它。 ### 三、最小堆：每次取全域最小 最後有一個解法是最難想到的寫法，而且做法也很漂亮，是透過 Heap 與 Linked List 的特性一起發揮出來的。 一開始把所有 Linked List 的 head 放入到 heap 裡面，透過他們的值來排序，接著就不斷地從 heap 裡面拿出值最小的節點，連接起來。在連接的時候要注意，連結完畢之後要將該節點往下移一格後，重新放回 heap 中。 **堆裡永遠只有 `k` 個節點**（每條串列各一個「當前最前面的」），所以每次取最小只要 $O(\log k)$，總共 $N$ 個節點就是 $O(N \log k)$ —— 和分治同級。 ## 解題方向 ### 循序合併 ```python # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: curr = head = ListNode() while l1 and l2: if l1.val < l2.val: curr.next = l1 l1 = l1.next else: curr.next = l2 l2 = l2.next curr = curr.next curr.next = l1 or l2 # 剩下的整條接上去 return head.next def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: res = None for li in lists: res = self.mergeTwoLists(res, li) return res ``` 最直觀，但複雜度最差。面試時可以先講這個確認方向，再說「不過這樣累積的結果會被重複走 k 次，我可以改成兩兩合併」。 ### 兩兩分治 ```python # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: curr = head = ListNode() while l1 and l2: if l1.val < l2.val: curr.next = l1 l1 = l1.next else: curr.next = l2 l2 = l2.next curr = curr.next if not l2: curr.next = l1 if not l1: curr.next = l2 return head.next def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: amount = len(lists) interval = 1 while interval < amount: for i in range(0, amount - interval, interval * 2): lists[i] = self.mergeTwoLists(lists[i], lists[i + interval]) interval *= 2 return lists[0] if amount > 0 else None ``` 用 `interval` 倍增取代遞迴，結果和遞迴分治一樣但不佔堆疊。合併後的結果一律存回 `lists[i]`，所以 `lists[0]` 最後就是答案。 ### 最小堆 ```python # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: q = [] heapq.heapify(q) for li in lists: if li: # id(li) 是這個解法比較要注意的地方。 heapq.heappush(q, (li.val, id(li), li)) curr = head = ListNode() while q: val, _, node = heapq.heappop(q) curr.next = node curr = curr.next node = node.next if node: heapq.heappush(q, (node.val, id(node), node)) return head.next ``` `curr = head = ListNode()` 是 dummy head，最後回傳 `head.next`，和 [21](/interview/coding/21-merge-two-sorted-lists) 是同一招。 ## 補充 ### 為什麼要塞一個 `id(node)` 唯獨一個 Python 中要注意的事情是，放入到 heap 時要在中間多給一個值，讓 heap 可以分辨出當有值相同的節點時，兩個節點其實並不同。 原因是 `heapq` 比較 tuple 時是**逐項比較**：第一項 `li.val` 相同時，它會去比第二項。如果 tuple 只有 `(val, node)` 兩項，Python 就會嘗試比較兩個 `ListNode` 物件 —— 而 `ListNode` 沒有定義 `<`，直接 `TypeError`。 塞一個**保證唯一而且可比較**的東西在中間就解決了。`id(node)` 是常見選擇；也可以用串列的索引 `i`，那個更容易解釋： ```python for i, li in enumerate(lists): if li: heapq.heappush(q, (li.val, i, li)) ``` **這個坑只有 Python 有** —— Java 的 `PriorityQueue` 可以直接傳 comparator，不會去比物件本身。 ### 合併家族 | 題目 | 資料結構 | 合併幾條 | 核心工具 | |---|---|---|---| | [21. Merge Two Sorted Lists](/interview/coding/21-merge-two-sorted-lists) | 鏈結串列 | 2 | dummy head + 兩指針 | | **23 這題** | 鏈結串列 | **k** | heap 或兩兩分治 | | [88. Merge Sorted Array](/interview/coding/88-merge-sorted-array) | **陣列**（原地） | 2 | **從後往前填** | 88 之所以要反過來做，是因為它要**原地寫回第一個陣列** —— 從前面寫會蓋掉還沒讀的元素。串列沒有這個問題，因為合併只是改指標。 [148. Sort List](/interview/coding/148-sort-list) 是同一個分治想法用在單一條串列上（找中點切兩半、各自排序、再合併）。Heap 的其他用法見 [Heap / Top K 模板](/interview/coding/heap-topk-template)。 ## 複雜度 設 `k` 是串列數量、`N` 是所有節點的總數。 **循序合併** - 時間 $O(kN)$ — 累積的結果被重複走了 `k` 次 - 空間 $O(1)$ — 只改指標 **兩兩分治** - 時間 $O(N \log k)$ — 每一輪把所有節點走一次（$O(N)$），總共 $\log k$ 輪 - 空間 $O(1)$ — `interval` 倍增的迭代寫法不佔堆疊（遞迴版是 $O(\log k)$） **最小堆** - 時間 $O(N \log k)$ — 每個節點各進出堆一次，堆的大小永遠是 `k` - 空間 $O(k)$ — 堆裡最多 `k` 個節點 其中 `k` 是串列數、`N` 是節點總數。 分治和堆是同一個時間量級，**分治的空間更省（$O(1)$ vs $O(k)$）**，但堆的程式碼比較短。面試時兩個都值得提，重點是講得出「為什麼循序合併是 $O(kN)$ 而這兩個是 $O(N \log k)$」。