企业官网建设流程全解析

链表相加（二）这类题，在算法题库里的定位很微妙：你说它难吧，核心操作无非遍历链表和进位；你说它简单吧，我自己见过不少人在面试时写错边界条件，也见过有人在“能不能修改原链表”这个前提上跟面试官反复拉扯。题面一般是这样：两个非空链表分别表示两个非负整数，每个节点只存一位数字，数字最高位在链表头部，比如 3->4->2 就表示 342。要你把两个数相加，返回一个新的链表，结果同样是高位在前。题目往往还会加一句，不要先把链表转成整数再相加。我第一次遇到这题时，脑子里冒出的第一个方案确实是“转成整数，加完再转回链表”，后来在真正动手实现时才意识到，这个思路既绕又危险。这篇内容，我就把这道题从思路上拆开，把反转、进位、边界这些关键点一次讲透。

1. 先别急着动代码，把“加法”翻译成链表操作

学链表相关的算法题，最大的误区是上来就写循环。链表相加（二）看起来是一个算术题，但核心难点并不在算术，而在于“存储顺序”和“计算顺序”不一致。

1.1 这道题其实在考什么

如果给你两个用数组存的数字，比如 [3,4,2] 和 [5,6,4]，数组下标天然从高位到低位，你照样没法直接从高位开始加，因为加法永远要从个位进位。链表的访问方式比数组更“死板”：你只有一个 next 指针，只能从头部一路走到尾部。换句话说，题目把数字的高位放在链表头部，就是为了让你不能顺着遍历顺序直接做加法。

所以这道题真正考察的有四件事：第一，链表的反转，需要一个可靠的迭代写法，不能每次现推；第二，逆序处理数据的能力，除了改指针，还要能想到栈这种数据结构；第三，进位的处理，尤其是连续进位和最后一位进位；第四，边界条件的敏感度，比如两个链表长度不一样，比如结果是 1000，中间的 000 不能丢，也不能多出前导 0。

我常跟准备面试的同学说，这种题刷的不是“会做”，而是“稳定不出错”。写一次对不难，难的是换了输入、换了限制条件还能写对。

1.2 手算类比与方案分叉

理解这道题，最直观的办法是回想手算加法的过程。假设你手里有两张纸条，从左到右依次写着千位、百位、十位、个位，但计算必须从最右边的个位开始。你有两个选择：第一种，把纸条整体倒过来，把个位放到最左边，然后从头开始算；第二种，从左到右把每一位抄到一沓纸上，抄完以后从最上面一张开始算，这其实就相当于栈的后进先出。

对应到代码里，第一种方案就是“反转链表法”，第二种就是“栈法”。反转链表法的空间复杂度可以做到 O(1)，但会修改输入链表；栈法的空间复杂度是 O(n)，但完全不碰原链表。很多面试题没有明说输入能不能修改，这种情况下栈法更安全。但如果你正在刷题，两种都应该写一遍，因为它们的操作侧重点完全不同。

2. 解法一：反转链表，把高位在前变成低位在前

这个方案的大方向是：先把 l1 和 l2 分别反转，让个位成为链表的头节点；然后像低位在前的那道简单题一样逐位相加；最后把结果链表再反转回来，恢复成高位在前。思路清晰，实现上有三个需要打磨的细节：反转函数怎么写、主循环怎么控制、最后怎么构建结果。

2.1 链表的反转三指针写法

反转单向链表是链表题的基本功，写法固定，最好能形成肌肉记忆。原理是维护三个指针：prev 指向已经反转好的部分，cur 指向当前要处理的节点，nxt 暂存 cur 的下一个节点。先把 nxt 保存下来，再把 cur.next 指回 prev，然后三个指针整体向后移动。

def reverse(head): prev = None cur = head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev

这里最容易被忽略的是nxt = cur.next这一步。如果不提前保存，把cur.next改成 prev 后，原来的下一个节点就找不到了，链表会在中途断掉。我见过很多初学链表的人在这里卡半天，其实就是没有理解“改指针之前先留后路”这件事。

2.2 逐位相加主循环：carry 是灵魂

反转之后，两个链表都是个位在前，接下来就可以模仿手算加法的步骤：每一位都等于 l1 当前节点的值加上 l2 当前节点的值，再加上上一位产生的进位。进位初始是 0，每轮计算完更新一次。

s = (r1.val if r1 else 0) + (r2.val if r2 else 0) + carry carry = s // 10 digit = s % 10

这里有个非常关键的习惯：取节点值的时候，不要直接写r1.val，因为两个链表长度可能不一样，短的链表会先走到 None。写成r1.val if r1 else 0，长短链表就能统一处理。我当时第一次写的时候没注意，结果两个链表一长一短就直接抛空指针异常。

还有一个容易漏掉的地方，主循环的条件必须包含 carry。你可以想象两个链表都走完了，但最后一位相加产生了进位，比如 999 + 1，最后只剩一个进位 1 需要生成一个新节点。如果循环条件只写while r1 and r2，这个进位的节点就会凭空消失。

2.3 完整示例代码：反转两次的版本

先给一个最直白的版本，反转两条输入链表，相加，再把结果反转回来，全程用一个 dummy 节点串起结果链表。

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverse(head): prev = None cur = head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev def add_two_numbers(l1, l2): r1 = reverse(l1) r2 = reverse(l2) dummy = ListNode() cur = dummy carry = 0 while r1 or r2 or carry: s = (r1.val if r1 else 0) + (r2.val if r2 else 0) + carry carry, digit = divmod(s, 10) cur.next = ListNode(digit) cur = cur.next if r1: r1 = r1.next if r2: r2 = r2.next return reverse(dummy.next)

这个版本很好理解：第一次反转让输入链表变成低位在前，相加过程就和一个简单的逐位加法一模一样，最后再反转一次让结果恢复高位在前。它的时间复杂度是 O(n)，额外的空间只有反转时那几个指针，可以视为 O(1)。

2.4 一个小优化：用头插法省掉最后一次反转

很多教程会直接反转结果，但我在反复写这道题之后，更喜欢用头插法构建结果链表。所谓头插法，就是每生成一个新节点，都把它插到当前链表的头部。因为新节点不断往前插，最后得到的链表自然就是高位在前，这样就能省去对结果链表的最后一次反转。

def add_two_numbers_v2(l1, l2): r1 = reverse(l1) r2 = reverse(l2) head = None carry = 0 while r1 or r2 or carry: s = (r1.val if r1 else 0) + (r2.val if r2 else 0) + carry carry, digit = divmod(s, 10) node = ListNode(digit) node.next = head head = node if r1: r1 = r1.next if r2: r2 = r2.next return head

注意这里的构建顺序：算出个位后，先把个位作为新节点插到头部，再算十位，再把十位节点插到个位前面，最后得到的头节点就是最高位。这个写法虽然看起来只有几行差异，但对链表方向的理解要求更高。我建议两种都写一遍，能帮你把“指针指向”这件事想得更清楚。

3. 解法二：用栈保序，不改动原链表

反转法写起来很顺手，但它有一个隐藏前提：输入链表可以被修改。如果面试官明确说不能动 l1 和 l2，或者你后续还要复用这两个链表，反转法就不合适了。这时候栈方案是最自然的替代。

3.1 栈为什么天然适配“从低位开始”

栈的核心特点是后进先出。把链表从头到尾遍历一遍，把每个节点的值依次压入栈，那么最后入栈的节点值就是数字的个位，第一个入栈的是最高位。出栈的时候，顺序恰好反过来，从个位开始。这个过程没有改动任何指针，只是把数据暂时存到了一个额外的结构里。

如果你觉得栈这个说法有点抽象，可以把栈想象成一摞盘子：链表遍历的顺序是从上往下放盘子，但你要取的时候只能从最上面取，于是最后放上去的个位反而第一个被取出来。这正是加法的执行顺序。

3.2 出栈相加与头插法构建结果

栈方案的代码框架和反转法很像，主要区别在于：不用写 reverse 函数，把 l1、l2 遍历入栈；相加时用pop()取出节点值；结果链表同样用头插法构建，保证高位在前。

def add_two_numbers_with_stack(l1, l2): s1 = [] s2 = [] while l1: s1.append(l1.val) l1 = l1.next while l2: s2.append(l2.val) l2 = l2.next head = None carry = 0 while s1 or s2 or carry: s = (s1.pop() if s1 else 0) + (s2.pop() if s2 else 0) + carry carry, digit = divmod(s, 10) node = ListNode(digit) node.next = head head = node return head

这个实现里，头插法的逻辑至关重要。如果你写的是head.next = node，结果链表永远只有一个节点，因为你没有更新头指针。正确顺序是先让新节点的 next 指向当前 head，再把 head 指向新节点。这个顺序我在初学的时候写反过不少次，后来养成了一个习惯：头插法一律先挂 next，再移动头指针。

3.3 空间复杂度说明

栈方案的时间复杂度同样是 O(n)，每个节点入栈一次、出栈一次。空间复杂度是 O(m + n)，m 和 n 分别是两个链表的长度。有人会觉得这个空间浪费，但这是“不能修改原链表”这个限制下的合理代价。面试时如果能主动说清这一点，比单纯闷头写代码更加分。

3.4 两种解法怎么选，一张表说清楚

刷题时我的建议是：如果你在本地练习，两种都写；如果是在面试现场，先确认“输入能不能改”。能改，优先反转法；不能改，直接说用栈。这个决策过程本身就是面试官想看到的。

4. 边界用例与现场排查实录

链表相加（二）最大的陷阱不在正常用例，而在边界。很多代码看着没问题，一跑特殊输入就翻车。这里我把最容易翻车的场景拿出来逐个拆解。

4.1 最容易翻车的三类输入

第一类，两个链表长度不一致。比如 l1 是 9->9->9->9->9，表示 99999，l2 是 1，表示 1。反转之后，r2 只有一个节点，循环里必须把缺失位当成 0 处理。如果直接用r2.val，第二个节点开始就会访问空指针。

第二类，连续进位。999 + 1 会从个位一直进到千位，最终结果是 1000，节点序列是 1->0->0->0。这里很容易丢掉最高位的 1，因为相加过程中每一步都有进位，最后一步循环结束时如果忘记把 carry 加进来，结果就变成 000。我习惯把循环条件写成while r1 or r2 or carry，用 carry 作为最后一位进位的保险。

第三类，两个数都是 0。0 + 0 的结果应该是一个值为 0 的节点，而不是一个空链表。有的实现会在 while 循环外只检查if carry == 0，然后用空链表表示结果，这是不对的。只要题目说“结果链表非空”，就必须确保至少生成一个节点。

4.2 运行代码前后的自查清单

写完代码先别急着提交，按这几条自查一遍：

• 循环条件是不是写成了while r1 and r2？如果两个链表长度不同，短的链表结束后循环就停了，剩下的高位全部丢失。
• 取节点值的时候有没有判空？要用val if node else 0这种写法。
• 最后一位进位有没有生成新节点？想想 999 + 1 这个用例。
• 反转链表时，nxt有没有在改指针前保存？
• 头插法构建结果时，是先连接node.next = head，再更新head = node？

这些点看起来零碎，但每一个都对应一次真实的运行报错或错误结果。我在给其他人 review 代码时，发现最频繁踩中的是第一个和第二个，尤其是循环条件，写顺手之后容易想当然。

4.3 常见问题速查表

这张表可以当做刷题后的复盘清单。每次写错，就把对应的行标记出来，第二次写之前扫一眼，能省下不少调试时间。

5. 面试中的延伸追问与实战建议

链表相加（二）作为一道常见算法题，面试官很少只考一个点。写完解法之后，大概率会有追问，追问的方向其实很固定。

5.1 如果链表改成低位在前怎么处理

最典型的变体是把高位在前改成低位在前，也就是个位在头节点。这种题反而更简单：不需要反转输入，也不需要栈，直接从头到尾逐位相加，结果链表也是低位在前。核心循环还是那套，while l1 or l2 or carry，只是少了逆序处理这一步。面试时如果你能说出两种题型的联系，会显得你不是在背代码，而是真正理解了加法顺序。

5.2 为什么不能先转成数字再相加

在一些强类型语言里，链表长度一旦超过整数位数，转成 int 或 long 就会溢出，这显然不是可靠方案。即便语言本身支持大整数，把链表转成数字再转回来，本质上是在回避链表的操作。面试官想看的不是你能不能算出结果，而是你如何处理逆序遍历、进位传播这些数据结构问题。所以这道题的正解，就是老老实实逐位相加。

我见过一个取巧版本：先把链表遍历成字符串，再转成大整数，加完后再把结果字符串拆成链表。不能说它算不出正确答案，但在算法面试的语境下，这种解法基本都会被追问得很难看。因为你绕开了题目真正想考查的部分。

5.3 同类变种题与训练建议

把这题刷透之后，我建议顺带练几道相近的题，比如合并两个有序链表、反转链表的两个相邻节点、求链表中间节点。这些题组合起来，几乎覆盖了链表操作的全部基础动作。练习时给自己定一个目标：不仅写对，还要把时间复杂度和空间复杂度说清楚，把“能否修改输入”和“结果是否需要反转”这两个判断点内化成思维习惯。

我自己在实际写这道题时，犯过的低级错误不在少数。第一次写栈法时，把node.next = head写反，结果链表永远只有一个节点；后来养成了一个习惯，凡是头插法构建链表，都会先用一个空的 head 变量，循环里先挂 next 再移动 head。另外，面试时如果被问到链表相加（二），建议先跟面试官确认清楚输入能否被修改；这一点看似小节，其实决定了解法选择。能改，就用反转法省空间；不能改，就直接报栈法。把这个顺序想明白，写代码的速度会快很多。