Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

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]

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]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

The Best Solution

Time complexity: O(max(m, n))
Space complexity: O(max(m, n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// runtime:3ms
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* curr = &dummy;
        int carry = 0;

        while (l1 || l2 || carry) {

            // 两个链表的对应位置相加
            if (l1) {
                carry += l1->val;
                l1 = l1 -> next;
            };
            if (l2) {
                carry += l2 -> val;
                l2 = l2 -> next;
            };

            // 取余，得到当前位置结果，拼在链表后
            curr -> next = new ListNode(carry % 10);
            // 除10，得到当前进位的值。留到下个位置的计算时判断是否需要进位使用。
            carry /= 10;
            // 移动链表指针到下一个。
            curr = curr -> next;
        }

        return dummy.next;
        
    }
};

以如下两数为例
l1 = [2,4,3]（表示 342），
l2 = [5,6,4]（表示 465）

目标是计算两数之和 807，输出应为 [7,0,8]。

初始状态

1
2
3
4
5
6
7

// dummy.val=0, dummy.next=nullptr（虚拟头节点）
ListNode dummy(0);  
// curr 指向 dummy（存储 dummy 的地址）
ListNode* curr = &dummy;  
// 进位初始为 0
int carry = 0;  
// l1 初始指向第一个节点（val=2），l2 初始指向第一个节点（val=5）

第一次循环（处理个位）

循环条件：l1（非空）|| l2（非空）|| carry（0） → 成立，进入循环。

1. 累加 l1 的值：carry += l1->val → carry = 0 + 2 = 2；l1 后移到下一个节点（val=4）。

2. 累加 l2 的值：carry += l2->val → carry = 2 + 5 = 7；l2 后移到下一个节点（val=6）。

3. 创建当前位节点：curr->next = new ListNode(7 % 10) → 新节点 val=7，curr->next 指向该节点（结果链表此时为 dummy -> 7）。

4. 更新进位：carry = 7 / 10 = 0。

5. curr 后移：curr = curr->next → curr 现在指向 val=7 的节点。

当前状态：

• 结果链表：dummy -> 7
• l1 指向 val=4 的节点，l2 指向 val=6 的节点，carry=0，curr 指向 val=7 的节点。

第二次循环（处理十位）

循环条件：l1（非空）|| l2（非空）|| carry（0） → 成立，进入循环。

1. 累加 l1 的值：carry += l1->val → carry = 0 + 4 = 4；l1 后移到下一个节点（val=3）。

2. 累加 l2 的值：carry += l2->val → carry = 4 + 6 = 10；l2 后移到下一个节点（val=4）。

3. 创建当前位节点：curr->next = new ListNode(10 % 10) → 新节点 val=0，curr->next 指向该节点（结果链表此时为 dummy -> 7 -> 0）。

4. 更新进位：carry = 10 / 10 = 1。

5. curr 后移：curr = curr->next → curr 现在指向 val=0 的节点。

当前状态：

• 结果链表：dummy -> 7 -> 0
• l1 指向 val=3 的节点，l2 指向 val=4 的节点，carry=1，curr 指向 val=0 的节点。

第三次循环（处理百位）

循环条件：l1（非空）|| l2（非空）|| carry（1） → 成立，进入循环。

1. 累加 l1 的值：carry += l1->val → carry = 1 + 3 = 4；l1 后移到 nullptr（已遍历完）。

2. 累加 l2 的值：carry += l2->val → carry = 4 + 4 = 8；l2 后移到 nullptr（已遍历完）。

3. 创建当前位节点：curr->next = new ListNode(8 % 10) → 新节点 val=8，curr->next 指向该节点（结果链表此时为 dummy -> 7 -> 0 -> 8）。

4. 更新进位：carry = 8 / 10 = 0。

5. curr 后移：curr = curr->next → curr 现在指向 val=8 的节点。

当前状态：

• 结果链表：dummy -> 7 -> 0 -> 8
• l1 为 nullptr，l2 为 nullptr，carry=0，curr 指向 val=8 的节点。

循环结束

判断循环条件：l1（空）|| l2（空）|| carry（0） → 不成立，退出循环。

最终返回

return dummy.next; → 返回 dummy 的下一个节点（即 val=7 的节点），整个结果链表为 [7,0,8]，符合预期。

关键总结

每次循环都会：

1. 累加当前位的数值（包括进位）；
2. 生成结果位的节点并挂到链表上；
3. 更新进位和指针位置。
   循环结束时，所有位和进位都已处理，最终通过 dummy.next 返回完整结果。