2. Add Two Numbers

題目 / Problem

中文： 給你兩個非空的鏈結串列（linked list），分別代表兩個非負整數。每個節點存放一位數字，而且數字是以反序（reverse order）儲存的——也就是說，個位數在最前面（鏈結串列的頭）。請把這兩個數字相加，並以同樣的鏈結串列形式回傳結果。

除了數字 0 本身以外，題目保證兩個數字都沒有前導零（leading zero）。

English: You are given two non-empty linked lists representing two non-negative integers. Each node holds a single digit, and the digits are stored in reverse order — the ones digit comes first (at the head of the list). Add the two numbers and return the sum as a linked list in the same format.

Except for the number 0 itself, both numbers are guaranteed to have no leading zeros.

Constraints / 限制： - 每個鏈結串列的節點數在 [1, 100] 範圍內 / Each list has between 1 and 100 nodes. - 0 <= Node.val <= 9 — 每個節點是一個 0~9 的數字 / each node is a single digit. - 題目保證數字沒有前導零 / no leading zeros in the input numbers.

Worked example / 範例：

Input:  l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]

因為 l1 反序後代表 342，l2 代表 465，342 + 465 = 807，807 反序寫成鏈結串列就是 [7,0,8]。 Because l1 reversed is 342 and l2 is 465, 342 + 465 = 807, and 807 written back in reverse order is [7,0,8].

名詞解釋 / Glossary

• 鏈結串列 / linked list：一種資料結構，由一串「節點（node）」組成。每個節點存一個值（val）和一個指向下一個節點的指標（next）。最後一個節點的 next 是空（NULL / nullptr）。它不像陣列那樣連續存放，而是靠指標一個接一個串起來。
• 節點 / node：鏈結串列的基本單位。這題的節點結構是 struct ListNode { int val; struct ListNode *next; }。
• 指標 / pointer：一個變數，裡面存的是「另一個東西的記憶體位址」。用 -> 可以透過指標存取節點的成員（例如 node->val）。
• 反序儲存 / reverse order storage：數字的個位數放在鏈結串列的頭。這其實對加法很方便，因為手算加法本來就是從個位（最低位）開始往上加。
• 進位 / carry：兩位數字相加超過 9 時要往下一位進 1。例如 7 + 5 = 12，本位寫 2，進位是 1。carry 這個變數就是拿來記住這個 1。
• 虛擬頭節點 / dummy node：一個「假的」開頭節點，不存實際資料，只是為了讓我們少寫一次「串列是不是空的？第一個節點怎麼接？」的判斷。最後回傳 dummy.next 就是真正的答案開頭。
• malloc / free（C 專用）：malloc(n) 向系統要一塊 n 位元組的記憶體並回傳它的位址；用來動態建立新節點。free 則是把記憶體還回去（這題交給 LeetCode 處理，我們不手動 free 答案）。

思路

最直覺的暴力想法是：把兩個鏈結串列各自「還原」成整數（例如把 [2,4,3] 讀成 342），相加後再把和拆成一個個數字放回鏈結串列。這個想法在數字很小時可行，但這題每個串列最多有 100 個節點，代表數字可能有 100 位數，遠遠超過 C 的 int 甚至 long long（最多約 19 位數）能表示的範圍，會發生溢位（overflow）。所以「先轉成整數」的路走不通。既然數字太大不能整個存起來，我們就模仿小學手算直式加法：一位一位加。而題目「反序儲存」這個設定剛好幫了大忙——個位數在最前面，我們從兩個串列的頭同時往後走，就是從最低位往最高位加，順序完全正確。核心變數是 carry（進位）：每一步算 sum = l1->val + l2->val + carry，本位數字是 sum % 10，進位變成 sum / 10。當某個串列比較短、走到底了，就把它當作 0 繼續加。這樣一路走到兩個串列都結束、而且 carry 也歸零為止。為了少寫特殊情況的判斷，我們用一個虛擬頭節點（dummy node）當結果串列的起點，用一個 tail 指標一直指著結果的最後一個節點，每算出一位就接一個新節點上去，最後回傳 dummy.next。

The brute-force idea is to convert each list back into an integer (read [2,4,3] as 342), add them, then split the sum back into digits. That works for tiny numbers but fails here: each list can have up to 100 nodes, so the numbers can be 100 digits long — far beyond what an int or even long long (~19 digits) can hold. It overflows. Since we can't store the whole number, we imitate grade-school column addition: add one digit at a time. The "reverse order" storage is a gift here — the ones digit sits at the head, so walking both lists from the front means adding from the least significant digit upward, exactly the order manual addition needs. The key variable is carry: at each step compute sum = l1->val + l2->val + carry, the digit for this position is sum % 10, and the new carry is sum / 10. When one list runs out, treat its remaining digits as 0. Keep going until both lists are exhausted and the carry is zero. To avoid fiddly special cases for the first node, we use a dummy head node as the anchor and keep a tail pointer at the last node of the result, appending one new node per digit, then return dummy.next.

逐步走查 / Walkthrough

輸入 / Input: l1 = [2,4,3], l2 = [5,6,4]（代表 342 + 465）。 初始 / Start: carry = 0，結果串列為空（只有 dummy）。

走查說明 / Notes: - 每一步 l1 和 l2 都往後移一格（l1 = l1->next）。/ Each step advances both l1 and l2 to ->next. - 第 2 步 4+6=10，本位寫 0、進位 1；這個 1 在第 3 步被加進去。/ Step 2 produces a carry that feeds into step 3. - 第 4 步兩個串列都空、carry 也是 0，所以停止，最終答案是 [7,0,8]。/ Both lists empty and carry 0 → stop; answer [7,0,8].

Solution — C

/*
 * 演算法 / Algorithm:
 * 從兩串列的頭（個位）同步往後走，逐位相加並維護進位 carry。
 * Walk both lists from the head (ones digit), add digit-by-digit while
 * carrying. Loop while either list has nodes OR carry is nonzero.
 * 用 dummy 虛擬頭節點簡化「接第一個節點」的邏輯。
 */

// LeetCode 已幫我們定義好 ListNode，這裡列出以供參考 / Provided by LeetCode:
// struct ListNode { int val; struct ListNode *next; };

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    // dummy 是虛擬頭節點，val 隨便給，重點是它的 next 會指向真正答案的第一個節點
    // dummy is a placeholder head; we only care about dummy.next at the end
    struct ListNode dummy;
    dummy.next = NULL;              // 先清空，避免指向垃圾位址 / init to NULL, avoid garbage

    // tail 一直指著「結果串列目前的最後一個節點」，新節點都接在它後面
    // tail always points at the last node of the result; we append after it
    struct ListNode* tail = &dummy; // &dummy 取 dummy 的位址 / take address of dummy

    int carry = 0;                  // 進位，初始沒有進位 / carry, starts at 0

    // 只要還有數字要加（任一串列非空），或還有進位沒處理完，就繼續
    // Continue while either list has nodes, or a carry remains
    while (l1 != NULL || l2 != NULL || carry != 0) {
        // 若 l1 走到底就當作 0，否則取它的值 / use l1's digit, or 0 if exhausted
        int x = (l1 != NULL) ? l1->val : 0;
        // 若 l2 走到底就當作 0，否則取它的值 / use l2's digit, or 0 if exhausted
        int y = (l2 != NULL) ? l2->val : 0;

        int sum = x + y + carry;    // 本位總和 = 兩位數字 + 進位 / column total
        carry = sum / 10;           // 整數除法取進位（0 或 1） / new carry (0 or 1)
        int digit = sum % 10;       // 取餘數得到本位要寫的數字 / digit for this position

        // malloc 向系統要一塊記憶體放新節點，sizeof 算出一個節點多大
        // allocate memory for one new node
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = digit;          // 存入本位數字 / store the digit
        node->next = NULL;          // 目前是最後一個，next 先設 NULL / it's the new tail

        tail->next = node;          // 把新節點接到結果串列尾巴 / append to result
        tail = node;                // tail 前進到這個新節點 / move tail forward

        // 兩個串列各自往後走一格（若還沒到底）/ advance each list if not exhausted
        if (l1 != NULL) l1 = l1->next;
        if (l2 != NULL) l2 = l2->next;
    }

    // 真正的答案從 dummy.next 開始（跳過虛擬頭）/ real answer starts after dummy
    return dummy.next;
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 與 C 版相同：從個位開始逐位相加並維護 carry，直到兩串列與進位都用完。
 * Same as the C version: add digit-by-digit from the ones place, maintaining
 * a carry, until both lists and the carry are exhausted. A dummy head node
 * removes the special case for appending the first node.
 */

// LeetCode 已定義 / Provided by LeetCode:
// struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // 虛擬頭節點，new 在堆積(heap)上建立一個節點 / dummy head created on the heap
        ListNode* dummy = new ListNode(0);
        // tail 指向結果串列最後一個節點，起點就是 dummy / tail tracks the last result node
        ListNode* tail = dummy;

        int carry = 0;              // 進位 / carry

        // 任一串列還有節點，或還有進位，就繼續 / loop while lists or carry remain
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            // 三元運算子：串列走到底就用 0 / ternary: use 0 when a list is exhausted
            int x = (l1 != nullptr) ? l1->val : 0;
            int y = (l2 != nullptr) ? l2->val : 0;

            int sum = x + y + carry; // 本位總和 / column total
            carry = sum / 10;        // 新進位 / new carry
            // emplace 一個新節點；此處直接 new 建立，值為本位數字 sum % 10
            // create a new node holding this position's digit
            tail->next = new ListNode(sum % 10);
            tail = tail->next;       // tail 前進 / advance tail

            // auto 這裡不需要，直接前進指標 / advance each list pointer if present
            if (l1 != nullptr) l1 = l1->next;
            if (l2 != nullptr) l2 = l2->next;
        }

        ListNode* head = dummy->next; // 真正答案的開頭 / the real head
        delete dummy;                 // 釋放虛擬頭，避免記憶體洩漏 / free the dummy node
        return head;
    }
};

複雜度 / Complexity

• Time: O(max(m, n)) — 設 m、n 是兩個串列的長度。我們對每一位只走一次，迴圈次數等於較長串列的長度（可能再多一位進位），所以時間跟較長的那個數字的位數成正比。/ We visit each digit position exactly once; the loop runs about max(m, n) times (plus at most one extra for a final carry).
• Space: O(max(m, n)) — 除了回傳的結果串列外，只用了固定幾個變數（carry、x、y…）。結果串列本身有 max(m,n) 或多一個節點，這是題目要求的輸出，屬於必要空間。/ Only a constant number of extra variables; the output list itself has max(m, n) (+1) nodes, which is required output.

Pitfalls & Edge Cases

• 忘記最後的進位 / Forgetting the final carry：像 [9,9,9] + [1] 會在最高位再產生一個進位（例如 999 + 1 = 1000）。迴圈條件加上 || carry != 0 就能多建一個節點放這個 1，否則答案會少一位。/ The last carry can create a brand-new highest digit; the carry != 0 in the loop condition handles it.
• 兩串列不等長 / Unequal lengths：短的先走到底。用「走到底就當作 0」的寫法（三元運算子）避免對 NULL/nullptr 解參考（dereference）造成崩潰。/ When one list ends, substitute 0 instead of dereferencing a null pointer.
• 想先轉成整數會溢位 / Overflow if you convert to int：數字可達 100 位，遠超 long long。逐位相加從根本上避開溢位。/ Numbers can be 100 digits — far beyond long long; digit-by-digit addition avoids overflow entirely.
• sum 的拆解方向 / Splitting sum：本位是 sum % 10（餘數），進位是 sum / 10（整數除法）。兩者搞反會得到完全錯誤的數字。/ Digit is sum % 10, carry is sum / 10; swapping them breaks everything.
• 回傳虛擬頭本身 / Returning the dummy：要回傳的是 dummy.next，不是 dummy。忘記跳過會讓答案多一個假的開頭。/ Return dummy.next, not the dummy itself.
• 記憶體 / Memory (C)：每個新節點都用 malloc；不要 free 回傳的答案串列（LeetCode 之後會用到並自行釋放）。C++ 版記得 delete dummy 這個不回傳的臨時節點即可。/ Don't free the returned list; in C++ only delete the non-returned dummy.