題目解釋
給定兩個已排序的 linked list list1
和 list2
的 head
。 將兩個 linked list 合併為一個排序過的 linked list。
這個 linked list 應該透過將前兩個 linked list 的 node 拼接在一起來形成。傳回 merged linked list 的 head。
範例
- 輸入:
list1 = [1, 2, 4], list2 = [1, 3, 4]
- 輸出:
[1, 1, 2, 3, 4, 4]
輸出就是合併後的 linked list。
最佳解法
步驟
- 先令一個空 Node
head
作為 linked list 的起點 - 初始化
curr
指標指向head
- 開始 traverse
list1
跟list2
- 數值小的優先成為
curr.next
- 總之要記得將
curr
前進一格 (curr = curr.next
)
- 數值小的優先成為
- 如果 traverse 完
list1
或list2
還有剩的話就直接將後面的部分加入curr
後面 (因為有 sorted 過)
NOTE: 要 return head.next
,因為 head 本身是一個 dummy node。
程式碼
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
head = ListNode(None, None)
curr = 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 head.next
時間複雜度
O(n + m)
,其中 n 是 list1
的長度,m 是 list2
的長度。
空間複雜度
O(1)
。
結語
基本上三個 test case 都有過就會全過的一題,也是高頻題。
Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)
- [推薦工具] 讓程式碼截圖變的美美的吧!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