LeetCode LCR 025. 两数相加 II
目录
题目描述
题意分析
给两条非空链表，每个节点存一个数位，最高位在链表头（也就是正常的书写顺序），把两个数相加并以同样的顺序返回结果链表。
竖式加法必须从个位算起，因为进位是从低位向高位传递的。而链表的头是最高位、只能从头往尾走，方向恰好与计算方向相反——这就是本题与「低位在前」版本的全部差异，也是难点所在。
题目额外要求不能修改输入链表，这条约束直接否掉了「把两条链都反转、算完再反转回来」这个最省事的做法（除非算完再把输入还原，写起来啰嗦且容易漏）。因此需要一种不改结构就能倒序访问的手段。
数位长度可能不等，短的那条要当作高位补零；结果长度可能比两者都长，例如
9 + 1会进位出一个新的最高位。数值范围提示也很关键：整数可能极长，不能先把链表转成
int或long相加再拆位，必然溢出，只能逐位模拟。
解法：数学推导
核心思路
先想暴力：把两条链表的数字拼成整数相加。链表长度可达上百位，任何定长整型都放不下，方案直接作废。这提醒我们必须停留在「逐位处理」的层面。
逐位处理要求从低位开始，而链表只能从高位开始。要解决方向冲突，可选的手段有三类：反转链表（但题目不许改结构）、递归到底再回溯（等价于用系统栈）、或者显式地把数位压进栈里。栈是「后进先出」，把链表从头压到尾之后，弹栈顺序恰好就是从个位到最高位——这正是我们需要的顺序，而且完全没有触碰原链表的指针。
于是状态定义为：
carry表示已处理低位产生的进位，取值只可能是 0 或 1；dummy.next始终指向当前已生成结果的最高位。每一轮把两个栈的栈顶（缺则补 0）与
carry相加，得到的和carry中，carry % 10是本位数字，carry / 10是新的进位。这里有个小技巧：直接把和累加进carry变量，用完再整除 10，省掉一个临时变量。结果的顺序问题同样要解决：我们是从个位往高位生成的，但输出要求高位在前。答案是头插法——每个新节点都插到
dummy之后，后生成的高位自然排在前面，输出即为正确顺序，而且不需要最后再反转一次。循环条件写成「两个栈还有元素，或者
carry非零」，这样999 + 1这种最高位进位的情况会自然地多跑一轮生成开头的1，无需任何特判。
解题步骤
- 两条链分别压栈：
for (; l1 != null; l1 = l1.next) s1.push(l1.val);，l2同理。只读val、只沿next走，输入链表一根指针都没改，满足「不修改输入」的要求。- 准备进位与哑结点：
carry = 0，dummy = new ListNode()。哑结点让头插法有一个固定的插入锚点，省掉「结果为空时特殊处理」的分支。- 循环条件写三项析取：
!s1.isEmpty() || !s2.isEmpty() || carry != 0。前两项负责把两条链的数位取完，第三项负责最高位的进位，缺了它5 + 5会漏掉开头的1。- 累加当前位：
carry += (s1 空 ? 0 : s1.pop()) + (s2 空 ? 0 : s2.pop())。短链弹空后补 0，等价于在高位补零对齐，不需要预先把两条链补成等长。- 头插新节点并更新进位：
node = new ListNode(carry % 10, dummy.next); dummy.next = node; carry /= 10;。新节点的next直接接上此前生成的最高位，插完再更新dummy.next。顺序不能反——先改dummy.next会让新节点接到自己身上。- 返回
dummy.next：它指向最终的最高位。以
l1 = 7 → 2 → 4 → 3、l2 = 5 → 6 → 4走一遍，即 7243 + 564 = 7807。压栈后s1从栈顶到栈底是3, 4, 2, 7，s2是4, 6, 5。第一轮：
carry = 0 + 3 + 4 = 7，头插节点7，结果为7，carry = 0。第二轮：carry = 0 + 4 + 6 = 10，头插节点0，结果为0 → 7，carry = 1。第三轮：carry = 1 + 2 + 5 = 8，头插节点8，结果为8 → 0 → 7，carry = 0。第四轮：s2已空补 0，carry = 0 + 7 + 0 = 7，头插节点7，结果为7 → 8 → 0 → 7，carry = 0。此时两个栈都空且carry为 0，循环退出，返回7 → 8 → 0 → 7，正是 7807。再看最高位进位的用例
l1 = 5、l2 = 5：第一轮carry = 10，头插节点0，carry = 1；两个栈都空但carry != 0，循环继续；第二轮carry = 1，头插节点1，结果为1 → 0，carry = 0，退出。返回1 → 0，即 10，正确。
代码实现
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> s1 = new ArrayDeque<>();
Deque<Integer> s2 = new ArrayDeque<>();
// 只读不改，压栈后弹出顺序即为从个位到最高位。
for (; l1 != null; l1 = l1.next) {
s1.push(l1.val);
}
for (; l2 != null; l2 = l2.next) {
s2.push(l2.val);
}
int carry = 0;
ListNode dummy = new ListNode();
while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
carry += (s1.isEmpty() ? 0 : s1.pop()) + (s2.isEmpty() ? 0 : s2.pop());
// 头插法：后算出的高位自动排到前面，省掉最后一次反转。
ListNode node = new ListNode(carry % 10, dummy.next);
dummy.next = node;
carry /= 10;
}
return dummy.next;
}
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
stack1 := []int{}
stack2 := []int{}
// 只读不改，出栈顺序即为从个位到最高位。
for l1 != nil {
stack1 = append(stack1, l1.Val)
l1 = l1.Next
}
for l2 != nil {
stack2 = append(stack2, l2.Val)
l2 = l2.Next
}
carry := 0
dummy := &ListNode{}
for len(stack1) > 0 || len(stack2) > 0 || carry > 0 {
if len(stack1) > 0 {
carry += stack1[len(stack1)-1]
stack1 = stack1[:len(stack1)-1]
}
if len(stack2) > 0 {
carry += stack2[len(stack2)-1]
stack2 = stack2[:len(stack2)-1]
}
// 头插法：后算出的高位自动排到前面。
node := &ListNode{Val: carry % 10, Next: dummy.Next}
dummy.Next = node
carry /= 10
}
return dummy.Next
}
复杂度分析
- 时间复杂度：$O(m+n)$，
m、n为两条链的长度。两次压栈各扫一遍，主循环轮数不超过 $\max(m,n)+1$，每轮只有常数次弹栈、取模与建节点。- 空间复杂度：$O(m+n)$，两个栈分别存下全部数位，这是「不修改输入又要倒序访问」付出的代价。返回的结果链表不计入额外空间。
关键点总结
- 数位在链表里但计算方向相反时，栈是把「顺序访问」翻成「逆序访问」的标准工具，代价是 $O(n)$ 空间，换来的是输入链表零改动。
- 用「
carry直接累加、再取模与整除」的写法，把本位与进位从同一个变量里取出，比另设sum更短且不易写错。- 循环条件必须把
carry != 0算进去，否则最高位的进位会被静默丢掉，这是所有大数加法的共同陷阱。- 头插法让生成顺序与输出顺序自动对齐，凡是「从后往前算、要求从前往后输出」的链表题都可以这样省掉一次反转。
- 短链弹空补 0 等价于高位补零，比预先把两条链补齐长度更省事，也避免了修改输入。
- 面试视角：先问清楚能否修改输入链表——能改就答「反转两条链、复用低位在前的解法、最后反转回来」，$O(1)$ 额外空间；不能改就答栈解法。主动比较这两条路线并说明各自代价，比只写出一种更能体现取舍能力。
易错点总结
- 循环条件漏掉
carry != 0：5 + 5会返回0而不是1 → 0，最高位进位被吞。- 头插时先改
dummy.next再建节点：写成dummy.next = node; node.next = dummy.next;会让节点指向自己，7243 + 564输出时死循环。- 改成尾插法却忘记最后反转：
7243 + 564会输出7 → 0 → 8 → 7，数位顺序整个颠倒。- 短链弹空时不补 0 而直接退出循环：
7243 + 564只算了三位就停，返回8 → 0 → 7，丢掉最高位的 7。- 把链表转成
long相加：数位可长达上百位，99...9 + 1会直接溢出，得到负数或截断结果。- 反转输入链表后不还原：题目要求不修改输入，判题在返回后校验原链表时会判错。
- 进位写成
carry = carry / 10之前就取了carry % 10存入变量却又用旧carry：例如先carry /= 10再new ListNode(carry % 10)，5 + 5会生成数字1而不是0，本位与进位对调。- Go 里循环条件写
carry > 0之外还漏判栈空：若写成for len(stack1) > 0 && len(stack2) > 0，长度不等时短链先耗尽，7243 + 564只输出低三位。- 用
Stack或按值传参把链表复制一份再反转：能过但多了一份 $O(n)$ 拷贝且逻辑更绕，面试时说不清「为什么不直接压栈」。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 445. 两数相加 II | 中等 | 与本题同题，可直接套用栈 + 头插的写法 |
| 2. 两数相加 | 中等 | 低位在前，方向天然一致，直接尾插逐位相加，不需要栈 |
| 369. 给单链表加一 | 中等 | 只加 1，可从右往左找第一个非 9 位，改动范围远小于通用加法 |
| 面试题 02.05. 链表求和 | 中等 | 同时考察正序与逆序两个版本，正序版即本题 |
| 61. 旋转链表 | 中等 | 同样需要「从尾部反推位置」，但靠成环再断开而非借助栈 |
| 143. 重排链表 | 中等 | 也需要逆序访问后半段，可用栈也可用反转，是本题空间取舍的另一个样本 |