題目解釋
給定一個由 k 個 linked list 組成的 array，每個 linked list 都是 ascending sorted 的。
將所有 linked list 合併為一個已排序的 linked list 並 return。
範例
- 輸入:
lists = [[1, 4, 5],[1, 3, 4],[2, 6]] - 輸出:
[1, 1, 2, 3, 4, 4, 5, 6]
lists 中的所有 linked lists 都被整合到同一條 linked list 了。
最佳解法
我們可以把這題拆解為
- Merge 兩條 linked list
- 逐步將
lists中的所有 linked list 合併 - 直到最後
lists中只剩下一條 linked list 時，return
說明
為了使用方便，
我們將 Merge 兩條 linked list 的邏輯 func 命名為 _merge_two_lists，
這是承襲自 【Leetcode 筆記】21. Merge Two Sorted Lists，
有興趣的讀者可以再回去複習。
分而治之法 (Divide and Conquer)
那關於合併的部分，我們必須用滾動的方式逐一將 linked list 們合併。
我們不斷向前滾動，traverse 整條 lists，
並 merge lists[i] 與 lists[i + 1]。
要注意的是取 lists[i + 1] 的時候要看有沒有越界，
如果越界的話就要把 lists[i + 1] 設成 None。
當上面的滾完一次後其實還遠遠沒有結束，
因為我們只是先兩步兩步的將 lists 中的元素合併，舉個例子：
[[1], [2], [3], [4], [5]]
=> [[1, 2], [3, 4], [5]] (第一次 iteration)
=> [[1, 2, 3, 4], [5]] (第二次 iteration)
=> [[1, 2, 3, 4, 5]] (第三次 iteration)在第三次 iteration 時，我們應該停止。
因此最後我們的 boundry condition 就是，
當 lists 中只剩下一條 linked list 時我們才停止，並回傳 lists[0]。
這邊隱含的概念就是 分而治之法 (Divide and Conquer)。
# Edge case handling
if not lists:
return None
if len(lists) == 1:
return lists[0]
# Divide and Conquer !
while len(lists) > 1:
merged_lists = []
for i in range(0, len(lists), 2):
list1 = lists[i]
if i + 1 < len(lists):
list2 = lists[i + 1]
else:
list2 = None
merged_lists.append(_merge_two_lists(list1, list2))
# Update current `lists` status
lists = merged_lists
return lists[0]完整程式碼在下方。
程式碼
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def _merge_two_lists(list1, list2):
new_head = ListNode()
curr = new_head
while list1 and list2:
if list1.val <= list2.val:
curr.next = list1
list1 = list1.next
else:
curr.next = list2
list2 = list2.next
curr = curr.next
if list1:
curr.next = list1
if list2:
curr.next = list2
return new_head.next
if not lists:
return None
if len(lists) == 1:
return lists[0]
while len(lists) > 1:
merged_lists = []
for i in range(0, len(lists), 2):
list1 = lists[i]
if i + 1 < len(lists):
list2 = lists[i + 1]
else:
list2 = None
merged_lists.append(_merge_two_lists(list1, list2))
lists = merged_lists
return lists[0]時間複雜度
O(n log k)，n 是 lists 的元素個數，k 是 linked list 的數量。
空間複雜度
O(1)，如果不考慮 linked list 節點本身佔用的空間。
該演算法的空間複雜度主要是由合併時新生成的 head 節點以及每次合併後的 merged_lists 佔用的空間，這部分是常數級別的。
結語
類似於 Merge Sort 的 linked list 題目。
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art
- [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
- [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
- [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26
