LeetCode 解題思路：2. Add Two Numbers（兩數相加）
鏈結串列的反向儲存與進位處理
目錄
題目描述
給定兩個非空的鏈結串列，代表兩個非負整數。它們每位數字都是按照反向的方式儲存的，並且每個節點只能儲存一位數字。
請你將這兩個數字相加，並以相同的形式返回一個表示和的鏈結串列。
你可以假設除了數字 0 之外，這兩個數字都不會以 0 開頭。
範例：
輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 465 = 807
輸入：l1 = [0], l2 = [0]
輸出：[0]
輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出：[8,9,9,9,0,0,0,1]
解釋：9999999 + 9999 = 10009998核心概念理解
為什麼要反向儲存？
反向儲存讓我們可以從最低位（個位數）開始相加，這與手算加法的順序一致：
342
+ 465
-----
從個位開始：2+5=7
十位：4+6=10，寫0進1
百位：3+4+1(進位)=8
結果：807在鏈結串列中：
2 → 4 → 3 (代表 342)
+ 5 → 6 → 4 (代表 465)
-----------
7 → 0 → 8 (代表 807)需要處理的情況
- 不同長度：一個鏈結串列比另一個長
- 進位處理：兩數相加 ≥ 10 需要進位
- 最後的進位：最高位相加後可能還有進位（如 999 + 1 = 1000）
解法：模擬加法過程
思路
用一個指標逐節點遍歷兩個鏈結串列，模擬手算加法：
- 將對應位置的數字相加（加上進位）
- 計算當前位的值（總和 % 10）和新的進位（總和 / 10）
- 建立新節點儲存當前位的值
- 移動到下一個節點
程式碼
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def addTwoNumbers(l1, l2):
# 建立虛擬頭節點，簡化邏輯
dummy = ListNode(0)
current = dummy
carry = 0 # 進位
# 當還有節點需要處理，或還有進位時
while l1 or l2 or carry:
# 取得當前位的值（若該鏈結串列已結束則為0）
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
# 計算總和
total = val1 + val2 + carry
# 計算當前位的值和新的進位
carry = total // 10
digit = total % 10
# 建立新節點
current.next = ListNode(digit)
current = current.next
# 移動指標
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next演算過程示例
l1: 2 → 4 → 3 (342)
l2: 5 → 6 → 4 (465)
初始：carry = 0, dummy → None
步驟1：
val1=2, val2=5, carry=0
total = 2+5+0 = 7
digit = 7, carry = 0
結果：dummy → 7
步驟2：
val1=4, val2=6, carry=0
total = 4+6+0 = 10
digit = 0, carry = 1
結果：dummy → 7 → 0
步驟3：
val1=3, val2=4, carry=1
total = 3+4+1 = 8
digit = 8, carry = 0
結果：dummy → 7 → 0 → 8
步驟4：
l1=None, l2=None, carry=0
迴圈結束
返回：7 → 0 → 8 ✓處理不同長度的例子
l1: 9 → 9 → 9 → 9 → 9 → 9 → 9 (9999999)
l2: 9 → 9 → 9 → 9 (9999)
步驟1-4：每步都是 9+9=18，digit=8, carry=1
結果：8 → 8 → 8 → 8
步驟5-7：l2已結束，9+0+1=10，digit=0, carry=1
結果：8 → 8 → 8 → 8 → 0 → 0 → 0
步驟8：l1和l2都結束，但carry=1
total = 0+0+1 = 1
結果：8 → 8 → 8 → 8 → 0 → 0 → 0 → 1 ✓複雜度分析
- 時間複雜度：O(max(m, n))
- m 和 n 分別是兩個鏈結串列的長度
- 需要遍歷較長的那個鏈結串列
- 最壞情況可能多一個節點（最後的進位）
- 空間複雜度：O(max(m, n))
- 建立了一個新的鏈結串列來儲存結果
- 結果鏈結串列的長度最多為 max(m, n) + 1
程式碼技巧解析
1. 虛擬頭節點（Dummy Head）
dummy = ListNode(0)
current = dummy- 為什麼用？ 避免特殊處理第一個節點
- 好處： 統一的插入邏輯，最後返回
dummy.next即可
2. 處理不同長度
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0- 當某個鏈結串列已結束時，將其值視為 0
- 避免分別處理剩餘部分
3. 迴圈條件
while l1 or l2 or carry:l1 or l2：還有節點需要處理or carry：處理最後的進位（如 99 + 1 = 100）
4. 進位計算
carry = total // 10 # 整數除法取商
digit = total % 10 # 取餘數//：向下取整除法（Python 3）%：取餘數運算
常見錯誤與注意事項
❌ 錯誤1：忘記處理最後的進位
# 錯誤的迴圈條件
while l1 or l2: # 忘記 or carry問題： 99 + 1 = 100 時，最後的 1 會遺失
❌ 錯誤2：改變原始鏈結串列
# 錯誤：直接修改 l1
l1.val = digit問題： 可能會影響其他使用這些鏈結串列的程式碼
❌ 錯誤3：不同長度時處理不當
# 錯誤：沒有檢查 l1 是否為 None
while l1:
val1 = l1.val # l1 可能為 None 導致錯誤延伸思考
如果是正向儲存怎麼辦？
l1: 3 → 4 → 2 (342)
l2: 4 → 6 → 5 (465)方法1： 先反轉鏈結串列，計算後再反轉回來 方法2： 用堆疊儲存，從最低位開始處理 方法3： 遞迴處理（需要先知道長度）
相關題目
- LeetCode 445: Add Two Numbers II（正向儲存版本）
- LeetCode 67: Add Binary（二進位字串相加）
- LeetCode 43: Multiply Strings（字串相乘）
重要觀念總結
- 虛擬頭節點：處理鏈結串列時的常用技巧，簡化邊界情況
- 進位處理：數字相加的核心邏輯，需要額外變數記錄
- 不同長度處理：用條件判斷取值，統一邏輯
- 迴圈條件設計：要考慮所有可能的終止情況
練習建議
- 先在紙上手算幾個例子，理解進位過程
- 實現基本版本，測試同長度的情況
- 測試不同長度的情況（一長一短）
- 測試邊界情況（有最後進位、全是 9）
- 嘗試實現正向儲存的版本
這道題是理解鏈結串列操作和數學運算結合的經典題目，掌握進位處理和虛擬頭節點技巧，對解決其他鏈結串列問題很有幫助！