第4章｜链表
Unit 11 · 两条链同步遍历与进位状态
链表中的数字相加，
让进位沿着 next 传播。
两个输入节点提供当前位，carry 保存上一位留下的唯一历史信息，tail 把当前结果数字接到答案链表末尾。无需先还原整个整数。
检测到上次学习记录可以恢复阶段、动画、代码、迁移脚手架和滚动位置。
LeetCode #2 题目模型逆序数字 · 非空链表 · 每个节点保存一位
题目要求
给定两个非空链表，分别表示两个非负整数。数字按照逆序存储，每个节点保存一位数字。请将两数之和也以同样形式返回。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(
self,
l1: Optional[ListNode],
l2: Optional[ListNode]
) -> Optional[ListNode]:
pass
- 每条链表节点数为 1–100；
- 每个节点值在 0–9；
- 除数字 0 外，没有前导零。
示例
l1 = [2,4,3] 代表 342
l2 = [5,6,4] 代表 465
输出 [7,0,8] 代表 807
[9,9,9,9,9,9,9] + [9,9,9,9]
→ [8,9,9,9,0,0,0,1]
复杂度目标
每个输入节点访问一次：时间 O(max(m,n))；结果链表以外只维护常数个变量：额外空间 O(1)。
和 Unit 10 的联系：继续使用 dummy + tail，但“选择节点”变成“创建当前位”
Unit 10：合并有序链表
比较两个当前节点，把较小的原节点直接接到结果链。
→
Unit 11：两数相加
读取两个当前数字与 carry，创建一个结果数字节点，再由 tail 接入。
Reverse-order Digits
头节点保存个位，沿 next 依次是十位、百位。因此一次正向扫描正好符合手算从低位到高位的顺序。
Carry 进位
上一位计算传给当前位的状态，只可能是 0 或 1。它是跨节点传播的唯一历史信息。
Synchronized Traversal
两条链表不一定等长。某条链耗尽后，其当前位按 0 处理，另一条链继续前进。
Result Tail
dummy 固定答案入口，tail 指向结果链尾。每轮创建 digit 节点并接到 tail.next。
1 读懂位序
2 体验整型转换
3 建立逐位状态
4 不变量与边界
5 Python 联动
6 脚手架迁移
认知任务 1
先确认：链表头节点究竟表示哪一位？
不要急着写代码。若位序读反，后续所有指针和进位逻辑都会建立在错误的问题表示上。
链表逐位加法实验标准示例：342 + 465
当前位计算尚未开始
carry 输入0
digit 输出—
carry 输出—
1. 还原整数2×1 + 4×10 + 3×100 = 342
2. 整数相加342 + 465 = 807
3. 再拆成链表807 → 7 → 0 → 8
读取两位
加入 carry
计算 total
拆 digit
更新 carry
接到 tail
头节点对应 10⁰ 位，因此可以从链表头开始直接做竖式加法。
当前状态契约变量含义不能漂移
核心循环不变量进入第 i 轮时，结果链表已正确保存前 i 个低位；carry 是这些低位传给第 i 位的唯一未处理信息。
当前位 i0（个位）
l1 当前值2
l2 当前值5
carry0
taildummy
结果链[]
若某条输入链已经耗尽，该位值按 0 处理；只要 l1、l2 或 carry 仍存在，就必须继续循环。
已处理位数0
创建节点数0
整型转换额外阶段0
[2,4,3] 代表哪个整数？
先根据“头节点保存个位”还原数字。
补全 LeetCode 可提交代码只填写 9 个关键表达式
from typing import Optional
class Solution:
def addTwoNumbers(self, l1, l2):
dummy = ListNode()
tail = dummy
carry = 0
while :
value1 = l1.val if l1 else
value2 = l2.val if l2 else
total =
carry, digit = divmod(, )
tail.next =
tail =
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return
完成代码或播放完整轨迹后解锁迁移；查看提示和填入骨架不会解锁。
分层认知提示
代码—输入节点—carry—结果链逐行联动1 / 1
l1n1
l2m1
carry0
digit—
result[]
进入函数，尚未创建结果节点。
完成代码联动后进入 LeetCode #445 官方迁移路径只有主代码正确或播放完整轨迹才会解锁；提示与补零骨架不计为完成。
迁移题：LeetCode #445「两数相加 II」
局部加法公式不变，但输入改为最高位在前。你需要先确认官方边界，再把“读取顺序”和“结果构造方向”重新设计。
迁移路径：官方读题 → 结构对照 → 四个语义槽位 → 官方样例轨迹与独立重写。每一步都需要完成当前任务才能进入下一步。
LeetCode #445 · Add Two Numbers II · Medium打开官方原题 ↗
官方任务
给定两个非空链表表示两个非负整数。每个节点保存一位数字，且最高位在链表头部。返回同样按最高位在前表示的和。
class Solution:
def addTwoNumbers(
self,
l1: Optional[ListNode],
l2: Optional[ListNode]
) -> Optional[ListNode]:
pass
进阶要求：在不反转输入链表的前提下完成。
示例与约束
[7,2,4,3] + [5,6,4]
→ [7,8,0,7]
→ [7,8,0,7]
[2,4,3] + [5,6,4]
→ [8,0,7]
→ [8,0,7]
[0] + [0] → [0]
- 每条链表节点数为 1–100；
- 节点值在 0–9；
- 除数字 0 外，不含前导零。
读题检查 1：链表 [7,2,4,3] 表示哪个整数？
观察最高位是否位于 head。
读题检查 2：进阶要求排除了哪种直接做法？
区分“反转输入结构”与“使用辅助栈”。
#2 与 #445：公式不变，信息访问方向改变
| 维度 | #2 两数相加 | #445 两数相加 II |
|---|---|---|
| 输入位序 | 最低位在 head | 最高位在 head |
| 下一计算位 | 沿 next 直接得到 | 先入栈，再从栈顶弹出 |
| 局部公式 | total = value1 + value2 + carrycarry, digit = divmod(total, 10) | |
| 结果构造 | tail 向后追加 | 新节点头插到当前 head 前 |
| 最终进位 | 循环条件都必须包含 carry | |
按依赖顺序排列迁移流程
先获得从低位到高位的访问能力，再复用局部加法，最后恢复正序输出。
四个语义槽位：每个槽位只承担一种职责
槽位 1｜保存正序输入
遍历两条链表，将当前节点的一位数字保存到对应栈。
槽位 2｜完整循环条件
栈可能长度不同，最后 carry 也可能单独产生最高位。
槽位 3｜复用局部加法
空栈按 0，弹出当前最低位，再计算 total。
槽位 4｜恢复正序输出
低位先算，但答案要求最高位在前，因此每轮头插。
stack1, stack2 = [], []
# 扫描两条正序链表，将 val 入栈
carry, head = 0, None
while stack1 or stack2 or carry:
value1 = stack1.pop() if stack1 else 0
value2 = stack2.pop() if stack2 else 0
total = value1 + value2 + carry
carry, digit = divmod(total, 10)
head = ListNode(digit, head)
return head
官方样例轨迹：7243 + 564 = 7807
stack1 · 底 → 顶
＋
stack2 · 底 → 顶
head = None
先扫描两条输入链，将数字依次压栈。
value1—
value2—
carry 输入 → 输出0 → 0
digit—
当前结果None
独立重写：不要复制组装代码
完整运行样例后，根据四个语义槽位独立写出可提交解法。检查器关注结构职责，不要求变量名完全一致。
必须先完整运行官方样例，才能提交独立重写。
完成后停留在本页
手动进入 Unit 12 →可以继续重播连续进位、比较正序与逆序，或手动进入 Unit 12。
Unit 11 已完成。页面不会自动跳转；刷新后仍会恢复当前学习位置。
触发信号两个链表按位表示数字，需要同步相加
核心状态l1、l2、carry、dummy、tail
循环不变量结果链已正确保存全部已处理低位
核心公式carry, digit = divmod(value1 + value2 + carry, 10)
关键边界长度不同按 0 补位；最后 carry 仍要生成节点
复杂度时间 O(max(m,n))，额外空间 O(1)