LeetCode Add Two Numbers：鏈表大數相加原地修改長鏈表

題目大意

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

原地修改長鏈表策略

• 先遍歷得兩鏈表長度 len1, len2。
• 將較長鏈表作為結果載體，較短鏈表逐位疊加。
• 進位處理：短鏈表結束後，若仍有進位，繼續向長鏈表高位傳遞；若傳至最末仍有進位，新建節點掛在尾部。
• 無需額外空間（除可能的進位節點），時間 O(max(len1,len2))。

完整代碼 (C++)

struct ListNode { int val; ListNode *next; ListNode(int x):val(x),next(nullptr){} };

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if (!l1) return l2; if (!l2) return l1;
        int len1=0, len2=0;
        for (auto p=l1;p;p=p->next) ++len1;
        for (auto p=l2;p;p=p->next) ++len2;
        ListNode *longer = len1>=len2 ? l1 : l2;
        ListNode *shorter = len1>=len2 ? l2 : l1;
        ListNode *p = longer, *q = shorter;
        int carry = 0;
        ListNode *prev = nullptr;
        while (p && q) {
            int sum = p->val + q->val + carry;
            p->val = sum % 10; carry = sum / 10;
            prev = p; p = p->next; q = q->next;
        }
        while (p && carry) {
            int sum = p->val + carry;
            p->val = sum % 10; carry = sum / 10;
            prev = p; p = p->next;
        }
        if (carry) {
            prev->next = new ListNode(carry);
        }
        return longer;
    }
};

關鍵細節

• 空鏈表直接返回另一個。
• prev 記錄長鏈表最後處理節點，用於掛載進位節點。
• 原地修改破壞輸入鏈表，若題目要求不修改輸入，需改用新建鏈表法。

複雜度

• 時間 O(N)，空間 O(1)（不計輸出）。

總結

Add Two Numbers 考驗鏈表指針操作與進位邏輯。原地修改長鏈表是空間最優解法，面試中常被追問「不修改輸入如何做」，需準備雙版本。