給定兩個非空鏈結串列，代表兩個非負整數。數字以反向儲存，每個節點包含一個位數。將兩數相加並以鏈結串列形式回傳結果。
Example:
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807
Intuition
TIP
核心思路：模擬直式加法，從最低位開始逐位相加，注意進位處理。
- 數字已經反向儲存，所以頭節點就是最低位，正好符合加法從低位開始的順序
- 逐位相加，carry = sum / 10，digit = sum % 10
- 兩串列長度可能不同，需要處理其中一個先結束的情況
Approaches
1. Recursive — O(max(n, m)) / O(max(n, m))
- Idea: 遞迴處理每一位的加法，將進位傳遞給下一層
- Time:
O(max(n, m))- n、m 為兩串列長度 - Space:
O(max(n, m))- 遞迴呼叫堆疊
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
return add(l1, l2, 0)
}
private fun add(l1: ListNode?, l2: ListNode?, carry: Int): ListNode? {
if (l1 == null && l2 == null && carry == 0) return null
val sum = (l1?.`val` ?: 0) + (l2?.`val` ?: 0) + carry
val node = ListNode(sum % 10)
node.next = add(l1?.next, l2?.next, sum / 10)
return node
}
}⭐ 2. Iterative with Dummy Head — O(max(n, m)) / O(1)
- Idea: 使用 dummy head，逐位相加兩串列節點的值加上進位，建立新節點接到結果串列
- Time:
O(max(n, m))- 遍歷較長的串列 - Space:
O(1)- 除了輸出外只用常數空間
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
val dummy = ListNode(0)
var curr = dummy
var p1 = l1
var p2 = l2
var carry = 0
while (p1 != null || p2 != null || carry != 0) {
val sum = (p1?.`val` ?: 0) + (p2?.`val` ?: 0) + carry
carry = sum / 10
curr.next = ListNode(sum % 10)
curr = curr.next!!
p1 = p1?.next
p2 = p2?.next
}
return dummy.next
}
}WARNING
最後的 carry != 0 條件容易遺漏。例如 [9,9] + [1] = [0,0,1]，若忘記處理最後的進位，結果會少一位。
🔑 Takeaways
- Pattern: 鏈結串列的逐位運算（加法、乘法等）都遵循「模擬直式計算」的模式
- Key trick: while 條件中加入
carry != 0可以優雅地處理最後一位進位，避免迴圈結束後的額外判斷