LeetCode 2 Add Two Numbers：鏈表逐位相加進位處理完整遞歸/迭代實現

問題描述

兩個非空鏈表表示非負整數，**逆序存儲**（個位在頭）。逐位相加，返回和鏈表（亦逆序）。如 (2→4→3) + (5→6→4) = 7→0→8（342+465=807）。

迭代解法（標準）

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0), *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; }
        carry = sum / 10;
        tail->next = new ListNode(sum % 10);
        tail = tail->next;
    }
    return dummy.next;
}

遞歸解法

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    return add(l1, l2, 0);
}
ListNode* add(ListNode* l1, ListNode* l2, int carry) {
    if (!l1 && !l2 && !carry) return nullptr;
    int sum = carry;
    ListNode *n1=null, *n2=null;
    if (l1) { sum += l1->val; n1 = l1->next; }
    if (l2) { sum += l2->val; n2 = l2->next; }
    ListNode* node = new ListNode(sum % 10);
    node->next = add(n1, n2, sum / 10);
    return node;
}

進位處理細節

• 循環條件 l1 || l2 || carry 確保最高位進位不丟失。
• 空指針視為 0 參與相加。
• 新節點值 sum % 10，進位 sum / 10。

遞歸與迭代對比

推薦迭代寫法，生產環境更安全。

進階：不修改輸入、雙向鏈表、大整數相加

• 先反轉鏈表、相加、再反轉結果（或用棧存儲節點）。
• 若允許修改輸入，可直接在較長鏈表上原地修改，空間 O(1)。