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