Add Two Numbers

leetcode #2

• 兩個非空單向鏈表，每個節點存一個數字，代表一個整數的反向儲存形式（低位在前）。
• 計算兩數之和，並以相同形式回傳。
  Ex.:
  Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
  Output: 7 -> 0 -> 8
  解釋: 342 + 465 = 807

thoughts

• 使用兩個指針同時遍歷鏈表，模擬「逐位相加 + 進位」。
• 若某個鏈表較短，則視為 0。
• 最後若有進位，需補一個新節點。
• 時間：O(max(m, n))
• 空間：O(1)（除了輸出鏈表）

Kotlin

fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
    val dummy = ListNode(0)
    var p = l1
    var q = l2
    var curr = dummy
    var carry = 0

    while (p != null || q != null) {
        val x = p?.`val` ?: 0
        val y = q?.`val` ?: 0
        val sum = carry + x + y
        carry = sum / 10
        curr.next = ListNode(sum % 10)
        curr = curr.next!!
        p = p?.next
        q = q?.next
    }
    if (carry > 0) curr.next = ListNode(carry)
    return dummy.next
}

Followup

• 如果數字是 正向儲存（最高位在前，LeetCode 445），該怎麼改？
• 如果鏈表非常大（如數百萬位數），是否能用分治法？
• 如果要處理多個數字鏈表相加，該如何擴展？