两数相加

怎样从“2→4→3 表示 342（head 是个位），与 5→6→4 逐位竖式相加得 7→0→8。”推导出 链表 · 进位模拟，并证明每次状态变化都不会漏掉答案？

中心结论：六阶段：逆序数位 → 竖式对齐 → 逐位 sum/digit/carry → dummy 脚手架 → 99+1 边界 → 代码映射。

2 个逆序的链表，要求从低位开始相加，得出结果也逆序输出，返回值是逆序结果链表的头结点。

在本站主例中，2→4→3 表示 342（head 是个位），与 5→6→4 逐位竖式相加得 7→0→8。

算法最终需要得到或观察：结果链表 7→0→8,表示 807。

复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“链表指针接力”，明确答案需要观察什么。
2. 2状态只维护 当前位指针 l1/l2、进位 carry、结果链表尾指针。
3. 3转移每一步按照 六阶段：逆序数位 → 竖式对齐 → 逐位 sum/digit/carry → dummy 脚手架 → 99+1 边界 → 代码映射。
4. 4收尾读取 结果链表 7→0→8,表示 807。，并复核边界与复杂度。

画清每根 next 指针改变前后的归属，再写代码。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：当前位指针 l1/l2、进位 carry、结果链表尾指针。

需要注意的是各种进位问题。

极端情况，例如 ``` Input: (9 -> 9 -> 9 -> 9 -> 9) + (1 -> ) Output: 0 -> 0 -> 0 -> 0 -> 0 -> 1 ```

为了处理方法统一，可以先建立一个虚拟头结点，这个虚拟头结点的 Next 指向真正的 head，这样 head 不需要单独处理，直接 while 循环即可。另外判断循环终止的条件不用是 p.Next ！= nil，这样最后一位还需要额外计算，循环终止条件应该是 p != nil。

六阶段：逆序数位 → 竖式对齐 → 逐位 sum/digit/carry → dummy 脚手架 → 99+1 边界 → 代码映射。

执行过程中持续维护：当前位指针 l1/l2、进位 carry、结果链表尾指针。

正确性依赖以下不变量：每一位的结果只依赖当前位与 carry,与更高位无关。

面试时可以压缩为：dummy+尾指针,while(l1||l2||carry) 逐位求和写结点;短链补 0,最后 carry 非零再补一位。

落到当前题，执行机制可以压缩为：六阶段：逆序数位 → 竖式对齐 → 逐位 sum/digit/carry → dummy 脚手架 → 99+1 边界 → 代码映射。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1这不是 243 + 564，而是 342 + 465链表的 head 不是最高位，而是个位。LC2 故意倒着存，是为了让我们从 head 开始直接做竖式加法。 因为：这不是 243 + 564，而是 342 + 465
2. 2先高亮个位：2 + 5普通竖式从右往左加，链表刚好把最右边的个位放在最前面，所以不用反转链表。 因为：head 在个位，所以不必反转链表
3. 3Round 3：3 + 4 + 1 = 8百位加上飞来的 carry=1：3+4+1=8。carry 清零，结果链 dummy → 7 → 0 → 8，表示 807。 因为：每轮：取两位 + carry → digit + 新 carry
4. 4Round 1：9 + 1 + 0 = 10个位 9+1=10：写 0，carry=1。结果 dummy → 0。 因为：99 + 1：链表结束 ≠ 计算结束
5. 5Round 3：l1/l2 都没了，但 carry=1这就是为什么 while 必须包含 carry != 0。链表结束不代表计算结束，还要补结点 1，得到 0→0→1 表示 100。 因为：99 + 1：链表结束 ≠ 计算结束
6. 6sum 从 carry 累加每轮先把 carry 放进 sum，再按需加上 l1、l2 的当前位（没有则跳过）。 因为：过程懂了，再对照 Go 实现
7. 7digit 与 carry 拆分digit = sum % 10 写入新结点；carry = sum / 10 传给下一位。 因为：过程懂了，再对照 Go 实现
8. 8我现在应该记住什么逆序链表 + 竖式同向扫描 + 逐位进位 + dummy 脚手架 + while 含 carry —— 五句话串起整题。 因为：过程懂了，再对照 Go 实现

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// ListNode define
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func addTwoNumbers(l1 *ListNode, l *ListNode) *ListNode {
	head := &ListNode{Val: 0}
	n1, n, carry, current := 0, 0, 0, head
	for l1 != nil || l != nil || carry != 0 {
		if l1 == nil {
			n1 = 0
		} else {
			n1 = l1.Val
			l1 = l1.Next
		}
		if l == nil {
			n = 0
		} else {
			n = l.Val
			l = l.Next
		}
		current.Next = &ListNode{Val: (n1 + n + carry) % 10}
		current = current.Next
		carry = (n1 + n + carry) / 10
	}
	return head.Next
}

func main() {
    // 1. 主例
    //    输入：mode="add-two", values=[2,4,3], valuesB=[5,6,4]
    //    期望：结果链表 7→0→8,表示 807。
    //
    // 2. 失败 / 未命中
    //    检查：忘记最后 carry=1 时还要补一个新结点。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC21 合并两个有序链表；LC445 两数相加 II
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意2→4→3 表示 342（head 是个位），与 5→6→4 逐位竖式相加得 7→0→8。
2. 2重复复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。
3. 3优化六阶段：逆序数位 → 竖式对齐 → 逐位 sum/digit/carry → dummy 脚手架 → 99+1 边界 → 代码映射。
4. 4证明每一位的结果只依赖当前位与 carry,与更高位无关。
5. 5复杂度时间 O(max(m,n))，空间 O(1)