2. Add Two Numbers

📘 題目敘述

給你兩個非空的 linked list l1 與 l2，它們分別代表兩個非負整數。

數字的每一位會以反向順序儲存，且每個節點都只包含一個數字。

請把這兩個數字相加，並把總和以 linked list 的形式回傳。

你可以假設這兩個數字不包含任何前導零，除非這個數字本身就是 0。

條件限制

• 每個 linked list 的節點數量在範圍 [1, 100]
• 0 <= Node.val <= 9
• 保證 linked list 所代表的數字不會有前導零

🧠 解題思路

我用「直式加法」的概念，一位一位加，並用新 linked list 存答案。

• 因為位數是反著存（最低位在最前面），所以可以從 l1、l2 的頭開始同步往後加。
• 每一輪加法都會用到：
  • i1：本輪從 l1 拿到的數字（如果 l1 走完就當 0）
  • i2：本輪從 l2 拿到的數字（如果 l2 走完就當 0）
  • carry：上一輪留下來的進位
• 我用一個 dummy 當假頭，再用 tail 指向目前答案串列的尾巴，方便一直把新節點接在尾端。
• 迴圈條件用 while (l1 || l2 || carry != 0)：
  • 只要任一邊還有節點，或還有進位，就表示答案還沒算完。

所有變數

• l1：第一個輸入 linked list 的目前節點指標
• l2：第二個輸入 linked list 的目前節點指標
• dummy：答案 linked list 的假頭節點（用來簡化接串列）
• tail：答案 linked list 目前的尾巴節點指標
• carry：進位（每輪更新成下一輪要用的進位）
• i1：本輪取自 l1 的數字（沒有就 0）
• i2：本輪取自 l2 的數字（沒有就 0）
• sum：本輪相加總和 i1 + i2 + carry
• digit：本輪要放進答案節點的數字（sum % 10）

🪜 主要流程步驟

1. 建立答案串列的假頭與尾巴指標

• dummy 先當一個固定的起點
• tail 一開始指向 dummy
• carry 初始化為 0

2. 每一輪處理一個位數（直到兩邊都結束且沒有進位）

• 先把 i1、i2 設成 0
• 如果 l1 還存在，就令 i1 = l1->val
• 如果 l2 還存在，就令 i2 = l2->val

3. 算出本輪 digit 與下一輪 carry

• sum = i1 + i2 + carry
• carry = sum / 10
• digit = sum % 10

4. 用 new 建立新節點接到答案尾端，並更新尾巴

• tail->next = new ListNode(digit)
• tail = tail->next

5. 推進 l1、l2（如果它們還沒走完）

• 若 l1 存在：l1 = l1->next
• 若 l2 存在：l2 = l2->next

6. 回傳真正的答案頭

• 因為 dummy 是假頭，所以回傳 dummy.next

💻 程式碼實作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        int carry = 0;
        while (l1 || l2 || carry != 0) {
            int i1 = 0, i2 = 0;
            if (l1) {
                i1 = l1->val;
            }
            if (l2) {
                i2 = l2->val;
            }
            int sum = i1 + i2 + carry;
            carry = sum / 10;
            int digit = sum % 10;

            tail->next = new ListNode(digit); // 只像這位指標
            tail = tail->next; // 改尾巴

            if (l1) {
                l1 = l1->next;
            }
            if (l2) {
                l2 = l2->next;
            }
        }
        return dummy.next;
    }
};

🔗 題目連結

https://leetcode.com/problems/add-two-numbers/