@laigary.com~/interview/coding/23-merge-k-sorted-li….md$
$ cat ./coding/23-merge-k-sorted-lists.md
[Coding]·2023-01-29·13 min read

23. Merge k Sorted Lists

23. Merge k Sorted Lists

給 k 條已排序的鏈結串列，合併成一條。

思路

這一題有多個不同的做法，我喜歡先從已經有的概念來出發。第一個概念是我們已經知道 21. Merge Two Sorted Lists 的方法 —— 和 2 Sum 很像，我們如果知道了合併兩條，有沒有辦法延伸到合併 k 條？

一、循序合併：一條一條疊上去

其實是可以的。第一個方法就是我們先從第一個和第二個 Linked List 合併，並存到結果上，再來合併結果跟第三個⋯⋯依此類推，一直到合併第 k 個。

這個做法一定寫得出來，但效率不好：累積的結果會越來越長，而每次合併都要把它整條再走一遍。第 i 次合併時結果已經有大約 i * (N/k) 個節點，加總起來是 O(kN)。

二、兩兩分治：像合併排序那樣

其實這就很像是 148. Sort List —— 我們不用一個一個合併，我們可以兩兩合併就好。這樣合併的輪數就會從 k 次變成 O(log⁡k) 次。

關鍵差別在於：循序合併時，同一批節點被重複走了 k 次；兩兩合併時，每個節點在每一「輪」只被走一次，而總共只有 log⁡k 輪。

這裡要注意的就是數學的處理：如果說總共有偶數個 Linked List，每兩兩合併不會有太大的問題，可是如果是奇數個，那最後落單的要怎麼處理？或是偶數個 Linked List 合併之後變成奇數個了，那要怎麼處理？

其實不用太擔心，因為奇數偶數會一直重複出現。主要的概念是第一次處理完後變成剩下 k/2 要處理，再處理一次後剩下 k/4，接著是 k/8⋯⋯直到結束。落單的那條什麼都不用做，下一輪它自然會找到配對。

可以用這個方式去看看變化：

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(Nlog⁡k) —— 和分治同級。

解題方向

循序合併

# 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 次，我可以改成兩兩合併」。

兩兩分治

# 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] 最後就是答案。

最小堆

# 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 是同一招。

補充

為什麼要塞一個 id(node)

唯獨一個 Python 中要注意的事情是，放入到 heap 時要在中間多給一個值，讓 heap 可以分辨出當有值相同的節點時，兩個節點其實並不同。

原因是 heapq 比較 tuple 時是逐項比較：第一項 li.val 相同時，它會去比第二項。如果 tuple 只有 (val, node) 兩項，Python 就會嘗試比較兩個 ListNode 物件 —— 而 ListNode 沒有定義 <，直接 TypeError。

塞一個保證唯一而且可比較的東西在中間就解決了。id(node) 是常見選擇；也可以用串列的索引 i，那個更容易解釋：

        for i, li in enumerate(lists):
            if li:
                heapq.heappush(q, (li.val, i, li))

這個坑只有 Python 有 —— Java 的 PriorityQueue 可以直接傳 comparator，不會去比物件本身。

合併家族

題目資料結構合併幾條核心工具
21. Merge Two Sorted Lists鏈結串列2dummy head + 兩指針
23 這題鏈結串列kheap 或兩兩分治
88. Merge Sorted Array陣列（原地）2從後往前填

88 之所以要反過來做，是因為它要原地寫回第一個陣列 —— 從前面寫會蓋掉還沒讀的元素。串列沒有這個問題，因為合併只是改指標。

148. Sort List 是同一個分治想法用在單一條串列上（找中點切兩半、各自排序、再合併）。Heap 的其他用法見 Heap / Top K 模板。

複雜度

設 k 是串列數量、N 是所有節點的總數。

循序合併

  • 時間 O(kN) — 累積的結果被重複走了 k 次
  • 空間 O(1) — 只改指標

兩兩分治

  • 時間 O(Nlog⁡k) — 每一輪把所有節點走一次（O(N)），總共 log⁡k 輪
  • 空間 O(1) — interval 倍增的迭代寫法不佔堆疊（遞迴版是 O(log⁡k)）

最小堆

  • 時間 O(Nlog⁡k) — 每個節點各進出堆一次，堆的大小永遠是 k
  • 空間 O(k) — 堆裡最多 k 個節點

其中 k 是串列數、N 是節點總數。

分治和堆是同一個時間量級，分治的空間更省（O(1) vs O(k)），但堆的程式碼比較短。面試時兩個都值得提，重點是講得出「為什麼循序合併是 O(kN) 而這兩個是 O(Nlog⁡k)」。

--tags#Linked List#Heap#Classic
← cd ../codingcd ~