LeetCode 2 Add Two Numbers：鏈表相加模擬大整數加法

題目描述

兩個非負整數以**逆序**鏈表存儲 (個位在頭)，逐位相加返回結果鏈表 (亦逆序)。

例：(2→4→3) + (5→6→4) = 342 + 465 = 807 → (7→0→8)

模擬加法邏輯

• 同步遍歷兩鏈表，對應位相加 + 進位 `carry`。
• 新節點值 = `sum % 10`，`carry = sum / 10`。
• 任一鏈表未盡或 `carry > 0` 繼續循環。
• 哨兵節點簡化頭節點處理。

代碼實現 (C++ / Java)

// C++
class Solution {
public:
    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; }
            tail->next = new ListNode(sum % 10);
            tail = tail->next;
            carry = sum / 10;
        }
        return dummy.next;
    }
};

// Java
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), tail = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;
            if (l1 != null) { sum += l1.val; l1 = l1.next; }
            if (l2 != null) { sum += l2.val; l2 = l2.next; }
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
            carry = sum / 10;
        }
        return dummy.next;
    }
}

完整可運行 C++ 示例 (含輸入輸出)

#include 
using namespace std;

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

ListNode* createList(int n) {
    ListNode *head = nullptr, *tail = nullptr;
    for (int i = 0, x; i < n && cin >> x; i++) {
        ListNode *node = new ListNode(x);
        if (!head) head = tail = node;
        else { tail->next = node; tail = node; }
    }
    return head;
}

void printList(ListNode* head) {
    while (head) { cout << head->val << " "; head = head->next; }
    cout << endl;
}

int main() {
    int n = 3;
    ListNode* l1 = createList(n);
    ListNode* l2 = createList(n);
    Solution sol;
    ListNode* res = sol.addTwoNumbers(l1, l2);
    printList(res);
    return 0;
}

複雜度

• 時間：O(max(m,n))，單次遍歷。
• 空間：O(max(m,n)) 輸出鏈表 (不算輸出空間則 O(1))。