題目解釋
給定一個由 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 題目。
- [推薦工具] 讓程式碼截圖變的美美的吧!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