L2 两数相加

题目链接

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

题目描述

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

示例 1

输入： l1 = [2, 4, 3], l2 = [5, 6, 4]

输出： [7, 0, 8]

示例 2

输入： l1 = [0], l2 = [0]

输出： [0]

示例 3

输入： l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

输出： [8,9,9,9,0,0,0,1]

提示

• 每个链表中的节点数在范围 [1, 100] 内
• $0 \le \text{Node.val} \le 9$
• 题目数据保证列表表示的数字不含前导零

题解

这道题本质上只是模拟小学都学过的竖式加法，只是套了个链表的壳子，千万别被唬住！

简单分析：两个链表中的数字本身就是按照从低位到高位的顺序存储，因此不需要先把链表反转。我们只需要同时从两个链表的头结点开始，每次取出当前位，相加后生成结果链表中的一个新结点，再继续处理下一位即可。直接看代码：

class Solution 
{
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
        {
            ListNode* dummyHead = new ListNode(); // 输出答案前的虚拟头结点
            ListNode* pointer = dummyHead; // 遍历指针，初始指向虚拟头结点

            bool flag = false; // 记录当前是否有进位，初始时标记为没有进位

            while(l1 != nullptr || l2 != nullptr || flag) // 循环条件：l1 和 l2 有任意一个没有处理完或者进位未处理
            {
                int val1 = (l1 == nullptr) ? 0 : l1->val; // 如果 l1 不为空结点，则把当前值赋给 val1，否则赋 0
                int val2 = (l2 == nullptr) ? 0 : l2->val; // 如果 l2 不为空结点，则把当前值赋给 val2，否则赋 0
                int sum = val1 + val2; // 把当前值相加

                if(flag) // 如果当前有进位需要处理
                {
                    sum++;
                    flag = false; // 恢复标记
                }

                if(sum / 10 != 0) // 产生新的进位
                {
                    sum %= 10; // 对 10 取余，得出新的该位置的值
                    flag = true; // 标记改为 true，表示有进位
                }
                    
                ListNode* nowNode = new ListNode(sum); // 创建当前节点并写入当前值
                pointer->next = nowNode; // 当前节点连接到指针上
                pointer = pointer->next; // 指针移动到下一位

                if(l1 != nullptr) l1 = l1->next;
                if(l2 != nullptr) l2 = l2->next;
            }
            return dummyHead->next;
        }
};

ListNode* l1 和 ListNode* l2 是题目已经处理好的，直接传进来的两个输入链表的头结点，我们后面直接拿来用就行。

那首先要解决的就是构建我们的输出链表，需要先创建一个虚拟头结点：ListNode* dummyHead = new ListNode(); 它后面会指向真正的头结点，也就是需要 return 返回的结点。

dummyHead 不保存真正的计算结果，只放在输出链表的最前面，方便后续统一添加新结点。这样就不需要单独处理结果链表的第一个结点。

然后定义一个遍历指针：ListNode* pointer = dummyHead; 初始时指向虚拟头结点，后面会始终指向结果链表当前的最后一个结点。每计算出一位结果，就在 pointer 后面连接一个新结点，再让 pointer 向后移动。

接着使用 flag 这个 bool 类型的变量来标记是否产生了进位，true 表示有进位，false 表示没有进位。

现在，初始条件都已经准备好了，可以开始进入循环处理。循环条件是 l1 和 l2 有任意一个没有处理完，或者还有进位没有处理（比如最后两个数相加产生了进位，也不能不管哈）。进入循环后，先使用三目运算符判断当前结点是否为空，如果为空，就将这一位按 0 处理；如果不为空，就读取当前结点中的值。

接下来将当前位置的两个数字相加，然后处理上一位留下来的进位（如果有的话），之后再判断有没有新的进位。最终得到这一轮计算后的 sum 和 flag。

这里的进位处理其实也可以写得更简洁一些：

int carry = flag ? 1 : 0;
int sum = val1 + val2 + carry;
flag = sum >= 10;
sum %= 10;

这几行乍一看可能没有前面的 if 写法那么直观，但代码更加简洁，这里就不展开讲解了，感兴趣的话可以自己结合前面的写法对照理解一下，接下来继续看怎么构建结果链表并移动指针：

ListNode* nowNode = new ListNode(sum); // 创建当前节点并写入当前值
pointer->next = nowNode; // 当前节点连接到指针上
pointer = pointer->next; // 指针移动到下一位

if(l1 != nullptr) l1 = l1->next;
if(l2 != nullptr) l2 = l2->next;

最后，就可以用 sum 创建新的结果结点，然后将新结点接到结果链表末尾，再让 pointer 向后移动，使其重新指向当前最后一个结点。当前这一位处理完成后，l1 和 l2 也分别向后移动一位，这里要注意哦，由于两个链表长度可能不同，所以移动前都要先判断是否为空，避免访问空指针。这样一轮处理结束后，就继续进入下一轮计算，直到计算完成跳出循环。最后把真正的头结点 dummyHead->next 返回即可。

这道题我也借助 AI 补充了力扣提交代码之外的本地测试部分，可以直接在自己的编译器中输入数据并运行。完整代码已经整理到 GitHub：https://github.com/C571467648/blog。后续其他题目也会采用相同的方式整理，建议有需要的话一次性下载使用。如果觉得比较麻烦，或者只想研究题目本身，也可以直接在力扣平台研究 class Solution 部分的代码。

本题讲解就到这里啦，欢迎交流讨论~