給定兩個已排序的鏈結串列
list1和list2，將它們合併成一個排序的鏈結串列並回傳。新串列應由兩個串列的節點拼接而成。
Example:
Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]
Intuition
TIP
核心思路：用 dummy head 簡化邊界處理，每次比較兩個串列的當前節點，將較小的接上。
- 類似 Merge Sort 的合併步驟
- Dummy head 避免處理「新串列第一個節點」的特殊情況
- 當其中一個串列用完，直接接上另一個串列的剩餘部分
Approaches
1. Recursive — O(n + m) / O(n + m)
- Idea: 比較兩個頭節點，較小者的 next 指向遞迴合併的結果
- Time:
O(n + m)- n、m 為兩串列長度 - Space:
O(n + m)- 遞迴呼叫堆疊
class Solution {
fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
if (list1 == null) return list2
if (list2 == null) return list1
return if (list1.`val` <= list2.`val`) {
list1.next = mergeTwoLists(list1.next, list2)
list1
} else {
list2.next = mergeTwoLists(list1, list2.next)
list2
}
}
}⭐ 2. Iterative with Dummy Head — O(n + m) / O(1)
- Idea: 建立 dummy head，用一個 tail 指針追蹤合併串列的尾端，每次將較小的節點接上
- Time:
O(n + m)- 每個節點恰好處理一次 - Space:
O(1)- 只使用常數額外空間
class Solution {
fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
val dummy = ListNode(0)
var tail = dummy
var l1 = list1
var l2 = list2
while (l1 != null && l2 != null) {
if (l1.`val` <= l2.`val`) {
tail.next = l1
l1 = l1.next
} else {
tail.next = l2
l2 = l2.next
}
tail = tail.next!!
}
tail.next = l1 ?: l2
return dummy.next
}
}🔑 Takeaways
- Pattern: Dummy head 是鏈結串列題目的萬用技巧，凡是「建構新串列」的題目都優先考慮
- Key trick:
tail.next = l1 ?: l2一行搞定剩餘串列的接合，Kotlin 的 Elvis 運算符很方便