LeetCode 2中等链表 · 模拟
两数相加 图解题解
链表里藏着两个大数，逐位相加还要处理进位——模拟竖式，一遍搞定。
两数相加就是在做竖式加法，只是数字从个位开始顺着链表排好了：两个指针对齐从表头（个位）同步往后走，每位把 a + b + carry 算出来，对 10 取余写进新节点，整除 10 的进位带给下一位；哪条链走完了那位就当 0，最后若还剩进位就补一个节点——一遍扫完不回头。
这道题到底在问什么
两条链表各表示一个数(每个节点一位、个位在表头)，返回它们和的链表。
- 链表 A
- 2 → 4 → 3 (即 342)
- 链表 B
- 5 → 6 → 4 (即 465)
- 输出
- 7 → 0 → 8 (即 807)
最优解：一步一步想明白
- 3两个指针同时走，每位算 a + b + carry：结果对 10 取余是这一位的数字，整除 10 是进位带到下一位。哪条短了就当它是 0。最后如果还有进位，再补一个节点。
- 4carry = 0，结果 = 空两个指针 p 同时停在两条链的表头（个位）。进位 carry=0，结果链表还空着（虚线占位）。逆序存的好处：表头就是个位，直接从这里开始竖式加。
- 5carry = 0，结果 = 7个位：a+b+carry = 2+5+0 = 7，没满十。本位 7 = 7%10，进位 carry = 7//10 = 0。tail.next = ListNode(7)，结果链表长出第一个节点 7，tail 指向它。
- 6carry = 0，结果 = 7两个输入指针各往前走一格，来到十位 4 和 6（个位已结算，标灰）。结果链表的 tail 仍停在 7。
- 7carry = 1，结果 = 7→0十位：4+6+0 = 10，满十了！本位写 10%10 = 0，进位 carry = 10//10 = 1 带到下一位。结果链表接上 0，tail 前移。这一步的进位是最容易漏的地方。
- 8carry = 1，结果 = 7→0输入指针走到百位 3 和 4。注意手里还攥着上一位的进位 carry=1，这一位相加时要带上它。
- 9carry = 0，结果 = 7→0→8百位：3+4+carry(1) = 8，没满十。本位 8，进位归 0。结果链表长出第三个节点 8：7 → 0 → 8。
- 10carry = 0 → 不补节点两条输入链都走到头，指针变空。最后再看一眼 carry：这里 carry=0，不用补。如果它是 1（比如 5+5=10），还得再给结果链表接一个值为 1 的节点——这正是循环条件要带 carry 的原因。
- 11结果 = 7→0→8 (807)逐位相加、满十进一，返回的结果链表 7 → 0 → 8，就是 342 + 465 = 807。
- 14链表竖式加法的三件套：逐位 divmod 取「本位/进位」、短的补 0、哨兵起头。循环条件写成 l1 or l2 or carry 是优雅收尾的关键。
- 19把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。可以让小欧把这套「哨兵 + 进位」骨架陪你默写一遍。
⚠️ 容易写错的地方
✗ 错：循环只写 while l1 and l2
✓ 对：while l1 or l2 or carry
不等长、或最高位还有进位时会漏算
✗ 错：忘了最后的进位
✓ 对：carry 也作为循环条件
如 5+5=10，最后要补一个 1 节点
完整代码（Python / C++ / Java）
Python
class Solution:
def addTwoNumbers(self, l1, l2):
dummy = ListNode(0)
cur = dummy
carry = 0
while l1 or l2 or carry:
x = l1.val if l1 else 0
y = l2.val if l2 else 0
carry, digit = divmod(x + y + carry, 10)
cur.next = ListNode(digit)
cur = cur.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.nextC++
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* cur = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
int x = l1 ? l1->val : 0, y = l2 ? l2->val : 0;
int sum = x + y + carry;
carry = sum / 10;
cur->next = new ListNode(sum % 10);
cur = cur->next;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
return dummy.next;
}
};Java
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), cur = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int x = l1 != null ? l1.val : 0, y = l2 != null ? l2.val : 0;
int sum = x + y + carry;
carry = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}
}套路模板 · 链表竖式加法（挖空背骨架）
# ① 哨兵起头，省掉「第一个节点」的特判
dummy = tail = 新节点(); carry = 0
# ② 循环条件三件：A 没走完 或 B 没走完 或 还有进位
while (A 还在) or (B 还在) or (carry 非 0):
# ③ 短的那条当 0
s = (A 在?取A.val:0) + (B 在?取B.val:0) + carry
# ④ 一次拆出「进位」和「本位」
carry, digit = s // 10, s % 10
# ⑤ 本位接到尾巴，尾巴前移
tail.next = 新节点(digit); tail = tail.next
# ⑥ 两条各自前移（走完了就保持空）
A = A.next if A else None; B = B.next if B else None
return dummy.next # ⑦ 跳过哨兵什么时候能套这套骨架？
✓ 要把两个序列「逐位/逐项」对齐相加
✓ 有「向后传递的余量」(进位 / 借位 / 累计和)
✓ 两条可能不等长 → 短的补 0
三个必背的「别漏」点：
1. 循环条件一定带「还有进位」这一项
2. 哨兵 dummy 起头，最后 return dummy.next
3. 进位 = 和 // 10，本位 = 和 % 10（别写反）
迁移：正序存(LC445)→先反转或用栈；
字符串相加(LC415)→下标从尾往前同一套。复杂度
时间复杂度
O(max(m,n))
按较长的位数走
空间复杂度
O(max(m,n))
结果链表长度
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 两数相加 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么逆序存反而方便？+
逆序=个位在表头，从头往后加正好低位到高位，进位自然往后传，不用反转。
结束后还有进位怎么办？+
这份代码把 carry 写进了循环条件(while l1 or l2 or carry),进位会让循环自动多跑一轮把最高位接上(如 99+1=100),不用循环外另判;若循环只判 l1/l2,才需在循环外补接一个 carry 节点。
dummy 头节点的好处？+
统一「接第一个节点」和「接后续节点」，免去对头节点特判。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。