LeetCode 2 Add Two Numbers：鏈表模擬大整數相加 (原地構建結果)

問題描述

兩個非空鏈表表示兩個非負整數，數字**逆序**存儲 (個位在頭)。將兩數相加，返回和的鏈表 (同樣逆序)。例如：(2→4→3) + (5→6→4) = 7→0→8 (342+465=807)。

核心算法：同步遍歷 + 進位處理

同時遍歷兩鏈表，對應位相加加上進位，結果取模 10 存入新節點，進位 = 除 10。任一鏈表結束視為 0。最後若有進位補一節點。

關鍵代碼 (C++ 精簡版)

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    int carry = 0;
    while (l1 || l2 || carry) {
        int sum = carry;
        if (l1) { sum += l1->val; l1 = l1->next; }
        if (l2) { sum += l2->val; l2 = l2->next; }
        tail->next = new ListNode(sum % 10);
        tail = tail->next;
        carry = sum / 10;
    }
    return dummy.next;
}

關鍵點

• 哨兵節點：dummy 簡化頭節點處理。
• 循環條件：l1 || l2 || carry 完美覆蓋所有情況 (含最後進位)。
• 原地構建：直接 `new` 節點掛在 `tail` 後，無需額外數組/字符串轉換。
• 逆序存儲：正好符合從低位到高位的加法順序，無需反轉鏈表。

常見錯誤與修正

• ❌ 將鏈表轉為整數相加再轉回 → 溢出風險 (大整數)。
• ❌ 忘記處理最後進位 (如 5+5=10)。
• ❌ 修改輸入鏈表節點值 → 破壞輸入 (題目通常允許但不推薦)。

複雜度分析

• 時間：O(max(m,n)) — 單次遍歷。
• 空間：O(max(m,n)) — 結果鏈表長度。

總結

LeetCode 2 是「鏈表模擬大整數加法」的標準模板。核心是「哨兵節點 + 同步遍歷 + 進位傳播」。此模板直接擴展可解決「兩數相減、大整數乘法 (分治/FFT)、多數相加」等變體。