題目
#

題目簡述
#

給定兩個非空的 linked list，表示兩個非負整數。數字以反向順序存儲，每個節點包含一個數字。將兩個數字相加並以相同的 linked list 格式返回。

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807。

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]
Explanation: 0 + 0 = 0。

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Explanation: 9999999 + 9999 = 10009998。

解題思路
#

這題給定兩個非空的 linked list，代表兩個非負整數。
數字以反向順序儲存，每個節點包含一個數字。
將兩個數字相加並以相同的 linked list 格式回傳。

比如 l1 = [2,4,3] 代表數字 342，l2 = [5,6,4] 代表數字 465
相加後得到 807，回傳 [7,0,8]

這題我們需要模擬手動加法的過程，從最低位開始相加，處理進位。

例子說明
#

l1 = [2,4,3], l2 = [5,6,4]

我們需要模擬 342 + 465 = 807 的計算過程：

初始化：
- 建立 dummy 節點作為結果鏈表的頭
- res 指向 dummy，用於最後返回結果
- total 和 carry 初始化為 0
第一次迭代：
- l1.val = 2, l2.val = 5
- total = carry(0) + 2 + 5 = 7
- num = 7 % 10 = 7
- carry = 7 / 10 = 0
- 建立新節點 7，連接到結果鏈表
第二次迭代：
- l1.val = 4, l2.val = 6
- total = carry(0) + 4 + 6 = 10
- num = 10 % 10 = 0
- carry = 10 / 10 = 1
- 建立新節點 0，連接到結果鏈表
第三次迭代：
- l1.val = 3, l2.val = 4
- total = carry(1) + 3 + 4 = 8
- num = 8 % 10 = 8
- carry = 8 / 10 = 0
- 建立新節點 8，連接到結果鏈表
完成：
- 返回 res.next，即 [7,0,8]

完整程式碼
#

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(); // 建立虛擬頭節點，避免處理頭節點的特殊情況
        ListNode res = dummy; // 保存結果鏈表的頭節點，用於最後返回
        int total = 0, carry = 0; // total：當前位數的總和，carry：進位值

        // 當 l1 或 l2 還有節點，或者還有進位時，繼續計算
        while(l1 != null || l2 != null || carry != 0) {
            total = carry; // 初始化 total 為進位值

            // 如果 l1 還有節點，加上 l1 的值並移動到下一個節點
            if (l1 != null) {
                total += l1.val;
                l1 = l1.next;
            }

            // 如果 l2 還有節點，加上 l2 的值並移動到下一個節點
            if(l2 != null) {
                total += l2.val;
                l2 = l2.next;
            }

            int num = total % 10; // 計算當前位數的值（取餘數）
            carry = total / 10; // 計算進位值（取整數）

            // 建立新節點並連接到結果鏈表
            dummy.next = new ListNode(num);
            dummy = dummy.next; // 移動 dummy 指針到下一個位置
        }

        return res.next; // 返回結果鏈表（跳過虛擬頭節點）
    }
}