23. Merge k Sorted Lists

23. Merge k Sorted Lists

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

其實是可以的，第一個方法就是我們我們先從第一個和第二個 Linked List 合併，並存到第二個 Linked List 上，再來合併第二個跟第三個...依此類推，一直到合併第 k - 1 和第 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: List[ListNode], l2: List[ListNode]) -> 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[ListNode]) -> ListNode:
        if not lists:
            return None
        for i in range(1, len(lists)):
            l1 = lists[i-1]
            l2 = lists[i]
            lists[i] = self.mergeTwoLists(l1, l2)
        return lists[-1]

不過其實這就很像是 148. Sort List ，我們不用一個一個合併，我們可以兩兩合併就好。這樣在合併的過程所需要花費的時間就會變成 $log(N)$ 。

這裡要注意的就是數學的處理，如果說總共有偶數個 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

# 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: List[ListNode], l2: List[ListNode]) -> 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[ListNode]) -> 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

Head

最後有一個解法是最難想到的寫法，而且做法也很漂亮，是透過 Heap 與 Linked List 的特性一起發揮出來的。

一開始把所有 Linked List 的 head 放入到 heap 裡面，透過他們的值來排序，接著就不斷地從 heap 裡面拿出值最小的節點，連接起來。

在連接的時候要注意，連結完畢之後，要將該節點往下移一格後，重新放回 heap 中，唯獨一個 Python 中要注意的事情是，放入到 heap 時，要給一個隨機的值，讓 heap 可以分辨出當有值相同的節點時，兩個節點其實並不同。

# 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[ListNode]) -> ListNode:
        q = []
        heapq.heapify(q)
        for li in lists:
            if li:
                # id(ld) 是這個解法比較要注意的地方。
                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