2. Add Two Numbers

Medium

Description

給定兩個非空鏈結串列，代表兩個非負整數。數字以反向儲存，每個節點包含一個位數。將兩數相加並以鏈結串列形式回傳結果。

Example:

Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807

Intuition#

核心思路：模擬直式加法，從最低位開始逐位相加，注意進位處理。

數字已經反向儲存，所以頭節點就是最低位，正好符合加法從低位開始的順序
逐位相加，carry = sum / 10，digit = sum % 10
兩串列長度可能不同，需要處理其中一個先結束的情況

Approaches#

1: Recursive#

概念: 遞迴處理每一位的加法，將進位傳遞給下一層
時間複雜度: O(max(n, m)) - n、m 為兩串列長度
空間複雜度: 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#

概念: 使用 dummy head，逐位相加兩串列節點的值加上進位，建立新節點接到結果串列
時間複雜度: O(max(n, m)) - 遍歷較長的串列
空間複雜度: 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
    }
}

最後的 carry != 0 條件容易遺漏。例如 [9,9] + [1] = [0,0,1]，若忘記處理最後的進位，結果會少一位。

🔑 Takeaways#

Pattern: 鏈結串列的逐位運算（加法、乘法等）都遵循「模擬直式計算」的模式
關鍵技巧: while 條件中加入 carry != 0 可以優雅地處理最後一位進位，避免迴圈結束後的額外判斷