两数相加
Add Two Numbers
两个非负整数按逆序存放在链表里，逐位相加，返回同样逆序存放的和。
在力扣中练习题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 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 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
解题思路
逐位模拟 · 进位
像竖式加法一样，从低位到高位处理进位
链表是逆序存放的，头节点就是个位，正好符合竖式加法从低位算起的顺序。
每一位计算 a + b + carry，当前位写 sum % 10，新的进位是 sum / 10。用 dummy 哨兵挂结果链，tail 每次追加新节点。
第 1 位：8 + 2 + 进位 0 = 10，写 0，新进位 1。
两个个位相加可能超过 9，超过的部分必须带到下一位。
- carry
- 1
自拟主例是 998 + 92：前两位连续进位，第三位 9 + 0 + 1 仍然进位；两个加数都走完后，carry 还是 1，循环条件必须包含 carry，才能补出最高位的 1。
第 3 位：9 + 空 + 进位 1 = 10，写 0，新进位 1。
- carry
- 1
l1→ nulll2→ null两条链长度不同时，短链先变空，后续按 0 处理即可，不需要提前补齐。整个过程每个节点只访问一次，结果节点也是边算边建。
易错点
- 循环条件只写 l1 || l2：最高位进位会丢，998 + 92 会得到 090 而不是 1090。
- 先把 l1 指向 next 再读 val：当前位读到的就是下一个数。
- 把链表转成 int 再相加：链表可能远超 64 位整数范围。
递归 · 带进位返回
当前位建节点，剩下的位交给递归
写法更短，但递归深度等于较长链的长度，最坏需要 O(n) 调用栈；仅作对照。
递归把“处理当前位”和“处理剩余位”分开：先算 sum = carry + a + b，建当前节点，再递归处理 a->next、b->next 和新的进位。
终止条件是三个输入都为空/零：两个链表都走完且没有进位。这样最高位进位会自然多建一个节点。
它和迭代版的状态完全一致，只是把循环改成了调用栈。链表很长时递归可能溢出，工程上仍推荐迭代。
- 1若两个节点都为空且 carry 为 0，返回 null。
- 2计算当前和与进位，建立当前节点。
- 3递归处理剩余部分，接到当前节点后。
- 4返回当前节点。
易错点
- 终止条件漏掉 carry：最高位进位会丢。
- 递归参数里继续使用已经移动过的指针。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
l1 = [8,9,9]（998），l2 = [2,9]（92）carry = 0，结果链只有 dummy；l1、l2 指向两个数的最低位。
- carry
- 0
查看 C++ 代码
延伸阅读
- 逆序链表 + 进位是“大数加法”的常见模型；如果题目改成顺序存放，需要先反转或借助栈。
- 哨兵节点在“结果长度未知、需要不断追加”的场景里特别省事。