GreedyAbyss1. 一道链表题凭什么值得反复刷
1.1 热题100里的常青树
在刷题平台的热题100清单里，「两数相加」几乎是我见过最常被点名的链表题之一。题目本身不算难，但它的考察点非常密集：链表遍历、虚拟头节点、进位处理、边界情况、空间复杂度，再加上大数加法这个藏在题面背后的工程场景，一道题能串起的东西比想象中多得多。
我这些年帮不少候选人做过模拟面试，这道题出现的频率高得出奇。十次里面至少有六次，面试官会把这道题当作链表题的第一道或者第二道。原因很简单：它不像反转链表那样只有一个核心技巧，也不像合并两个有序链表那样边界相对整齐，它需要你在一个循环里同时处理两个链表的长度差、空指针、进位和节点创建。任何一个环节没想清楚，代码就会在边界处崩掉。
所以这篇文章不是简单给你一份能通过的Java代码，而是把这道题拆开揉碎：为什么链表适合模拟大数加法、标准迭代写法每一步在干什么、面试官会怎么追问、以及我在实际调试中总结出来的容易翻车的地方。
1.2 面试官到底在考察什么
很多人以为这道题考的是“你会不会操作链表”，实际上它考的是“你能不能把一个现实问题翻译成链表操作”。
题目描述通常是这样：给定两个非空的链表，每个节点只存一位数字，数字按逆序存储，也就是链头是个位、链尾是最高位。两个链表分别代表两个非负整数，要求返回一个新的链表，表示这两个数相加的结果。比如 2->4->3 和 5->6->4，对应的数分别是342和465，相加是807，返回的链表应该是 7->0->8。
面试官想看到的东西其实是三层。第一层，你知不知道用逐位相加加进位来处理，而不是把链表先转成整数再相加；第二层，你能不能写出一个循环，同时遍历两条链，并且正确处理一长一短；第三层，你愿不愿意把边界条件想全，尤其是最后一位还有进位的情况。这三层分别对应建模能力、编码能力和细心程度，恰好是工程开发里最基础的三个素质。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 先把链表和大数加法这两个底层模型揉清楚
2.1 链表节点的结构
Java里链表节点一般都长这样：
java复制public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
这道题只需要用到 val 和 next，没有 prev，所以它是一个单向链表。遍历单向链表的前提是，你必须用一个临时指针去移动，不能直接拿头节点乱动，否则回头想要 head 的时候发现已经找不到了。每个人写的第一版代码可能都犯过这个毛病，后面我会专门把这类问题列出来。
2.2 为什么天然适合模拟“逐位相加”
如果让你用int直接算，两个链表对应的数可能非常大。Java的 int 最多只能表示大约21亿，long 虽然更大，也就是19位十进制数左右。链表的长度没有这个限制，它可以有几百个甚至几千个节点，每个节点仍然只存一位数。这种“一个节点存一位，多个节点串成一个超长数字”的结构，天然是来模拟高精度大数运算的。
手工计算加法的过程大家都知道：从个位开始，一位一位对齐相加，如果某一位的和超过9，就向高位进1。链表恰好把个位放在头节点，所以只要从头部开始遍历，每一轮算一个位，把进位带给下一位，整个过程和手写加法一模一样。这就是这道题不需要把链表转成整数再运算的根本原因——转整数反而会溢出，而且丢失了链表的结构优势。
2.3 很多人想不明白的循环条件
我第一次写这道题的时候，下意识写的是 while (l1 != null && l2 != null)，结果两个链表长度不同的情况就处理不了。后来才意识到，正确写法应该是 while (l1 != null || l2 != null)。
原因在于，加法必须一直进行到较长的那个链表也结束为止。如果一个链表先变成 null，它这一位可以看作数字0，继续参与相加。换句话说，短的链表被隐式地“补零”了。这个思路非常重要，因为它统一了长度不等的逻辑：不需要先把长链表的剩余部分单独处理，只需要在循环里判断某个链表是否为空，为空就取0。
理解了这个之后，代码的结构就清晰了。每一次循环处理一位，从两个链表各自取一个数字，加上上一位的进位，得到这一位的和，然后记录新的进位，再把当前位的个位数挂到结果链表的末尾。循环结束后，如果进位还是1，说明最高位多了一个节点，必须额外补上。
3. Java实现：从第一版能过到最顺手的写法
3.1 基础实现：虚拟头节点法
先给出我最推荐的标准写法，这也是我在模拟面试里看到候选人写得最不容易出错的版本：
java复制public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int carry = 0;
while (l1 != null || l2 != null) {
int x = (l1 == null) ? 0 : l1.val;
int y = (l2 == null) ? 0 : l2.val;
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;
}
}
if (carry != 0) {
cur.next = new ListNode(carry);
}
return dummy.next;
}
这里用到了虚拟头节点 dummy。它的作用非常实际：如果不创建虚拟头节点，结果链表的第一个节点需要单独判断“当前是否为空”，为空就赋给头节点，不为空就接到 next 上。这一判断放到循环里不仅让代码变长，还容易在“第一次赋值”和“后续追加”之间出错。用 dummy 之后，循环里只需要无脑 cur.next = new ListNode(...)，最后返回 dummy.next 就是真实头节点。这个技巧在链表题里的通用性极强，合并链表、删除节点等场景都能用。
3.2 进位的处理时机
每一轮关键就两行：
java复制carry = sum / 10;
cur.next = new ListNode(sum % 10);
sum / 10 在个位数相加时，结果只可能是0或者1，因为两个一位数最大是9加9，加上进位1也就是19，商最多是1。用除法算进位，优点是不用额外写 if (sum >= 10)，也不会漏掉 sum 恰好等于10的情况。sum % 10 则是当前位最终应该显示的数字。
很多人会在算完 carry 之后把 carry 忘记清零，导致进位一直传递下去。其实只要每一轮都重新计算 carry = sum / 10，它天然会被下一轮覆盖，不需要单独做清零。这也是这个写法最让人安心的地方：状态是每轮从输入重新算的，而不是在上一次基础上累加的。
3.3 指针移动的先后顺序
细心的读者会发现，我在移动 l1 和 l2 之前，先做了 cur.next = ... 和 cur = cur.next。这个顺序是对的。因为 cur 是结果链表的尾指针，它必须先指向新节点，再移动到新节点，才能保证下一次 cur.next 是追加在末尾。
如果反过来，先移动 l1 或 l2 再移动 cur，结果一般也不会错，但逻辑上会让人多绕一层。我建议固定一个顺序：先取数、再算和、再更新进位、再挂节点、最后移动三个指针。这个顺序固定下来，写代码的时候不需要思考，出错概率会小很多。
3.4 时间复杂度和空间复杂度
循环次数取决于两个链表中较长的那一个，所以时间复杂度是 O(max(m, n))，其中 m 和 n 分别是两条链表的长度。空间复杂度方面，结果链表必然会有 max(m, n) 个或 max(m, n) + 1 个节点，因此是 O(max(m, n))。有些人会说这是 O(1) 额外空间，因为除了输出链表没有额外使用和输入规模相关的存储。这两种表述在面试里都能接受，但要注意和面试官统一口径。我一般会说“除了答案链表之外，只用了常数额外空间”。
3.5 递归解法和迭代解法的等价性
这道题也可以写成递归，核心思路是把“当前位相加 + 进位 + 递归处理下一位”拆开：
java复制public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
return add(l1, l2, 0);
}
private ListNode add(ListNode l1, ListNode l2, int carry) {
if (l1 == null && l2 == null && carry == 0) {
return null;
}
int x = (l1 == null) ? 0 : l1.val;
int y = (l2 == null) ? 0 : l2.val;
int sum = x + y + carry;
ListNode node = new ListNode(sum % 10);
node.next = add(
(l1 == null) ? null : l1.next,
(l2 == null) ? null : l2.next,
sum / 10
);
return node;
}
注意递归出口的条件是 l1 == null && l2 == null && carry == 0，这意味着如果最后还有一个进位，会继续创建一个值为1的节点。递归写法在逻辑上更简洁，但容易忽略“链表非常长时可能导致栈深度过大”的问题。面试的时候可以提一句：递归写法思路清晰，但在生产环境里可能存在栈溢出风险，所以更倾向于迭代写法。这会让面试官觉得你有工程思维。
4. 边界条件与面试追问：最容易翻车的几个点
4.1 两条链表长度不相等
例如 1->8 和 0，也就是18加0，结果是18。链表 0 只有一个节点，循环第一轮取 l1=1、l2=0，结果是1；第二轮 l1=8，l2 已经为 null，按照代码逻辑会取0，得到8，最后链表是 1->8，结果正确。关键在于 l2 为空时依然进入循环，而不是跳过这一轮。
如果面试官让你不用“空节点当作0”的写法，而是先处理公共部分、再处理长链表剩余部分，也能写出来，但代码会多出一个循环。那个写法不是错的，只是更容易遗漏最后的进位。我建议用统一取0的版本，因为它的状态转移更一致。
4.2 最高位额外进位
这是这道题最经典的坑：9->9->9 加上 1。逐位算下来：个位9加1得10，进位1，个位为0；十位9加进位1得10，进位1，个位为0；百位9加进位1得10，进位1，个位为0。循环结束后 carry 还是1，必须在末尾补一个值为1的新节点，最终链表是 0->0->0->1，也就是1000。
如果漏掉循环后的 if (carry != 0)，结果会变成 0->0->0，也就是0，错得离谱。这个 case 一定在写完之后手动验证。我见过太多候选人代码写得很快，但问他“999加1等于多少”时才发现自己漏了进位。
4.3 面试官常见的 follow-up 类型
这道题的追问方向其实很固定，我整理成一张表，方便你在面试前自查：
| 追问方向 | 考察点 | 建议回答思路 |
|---|---|---|
| 两个链表很长，直接转成整数可以吗？ | 大数溢出意识 | 不行，int和long都有位数上限，改成链表模拟更安全 |
| 能否不新建链表，直接改原链表？ | 空间优化能力 | 可以，但需要复用较长链表的节点，还要处理最后进位的新节点 |
| 如果链表是按高位在前的顺序存呢？ | 数据结构反转思维 | 需要先反转两条链表，再逐位相加，最后把结果反转回来 |
| 如果链表里存的是负数怎么办？ | 扩展建模能力 | 不能只按绝对值处理，需要考虑符号位和比较大小，复杂度更高 |
| 如果每一位不是十进制而是其他进制？ | 参数化思维 | 把 carry = sum / 10 改成 carry = sum / base 即可 |
这里最值得展开的是“如果链表是按高位在前存储”的变体。比如数字342存成 3->4->2，这时候个位在链表尾部，从头部开始遍历反而不能直接做加法。常规解法是先将两个链表反转，然后按逆序相加，最后再反转回来。这个变体在面试里非常常见，它能进一步考察你对链表反转是否熟练。我建议在准备这道题时顺手把反转链表也练熟，面试时如果需要，可以直接写出来。
5. 实战优化与工程化改造：从刷题到可维护代码
5.1 能否原地修改链表
很多人刷题只想着通过，但面试官喜欢追问“能不能少用一点空间”。上面标准解法里，结果链表是新创建的，每一步都 new ListNode，这本身没有问题，但在某些场景下可以考虑复用原链表节点。
具体做法是：先确定 l1 和 l2 哪个更长，把结果直接写到较长的那条链表上。循环过程中遇到较短的链表为 null 时，就只取另一个链表的值加上进位；如果最终还有进位，就在长链表末尾追加一个新节点。这样做能够把额外空间从 O(n) 降到 O(1)，但代码的可读性会下降，而且修改了输入数据。
我自己的看法是：刷题阶段优先保证代码正确和可读，面试时如果被问到空间优化，再口头给出方向即可。很多面试官并不指望你在二十分钟内写出原地修改的无 bug 版本，他们更在意你有没有意识到“新建链表不是唯一方案”。
5.2 可读性优化：把核心逻辑抽得更好懂
如果是在项目代码里写类似逻辑，我不会把取数和进位计算全部堆在一个循环里。我会拆成两个语义清晰的小方法，比如 getVal(ListNode node) 负责把空节点转换成0，getCarry(int sum) 负责计算进位。不过对于刷题代码，方法拆得太多反而显得绕。中间的平衡点是：用一个局部变量 x 和 y 表示当前位的两个加数，而不是在 sum 里直接写 (l1 == null ? 0 : l1.val)。这个细节能让每行都短一些，调试时也更容易看到当前到底取到了什么值。
5.3 如果先合并成字符串再反转，可行吗
有候选人问过我：能不能把链表里的数字先拼成字符串，再用大数工具类相加？理论上当然可以，比如Java里有 BigInteger，直接 new BigInteger(sb.toString()) 就能完成加法。但这样做有两点不好：第一，它绕过了链表这个核心考察点，面试官会觉得你没有理解题目的意图；第二，字符串转换和 BigInteger 内部实现的复杂度，不一定比直接逐位相加更优，尤其是链表很长时，构建字符串本身就要多花一次遍历。
这道题名为“两数相加”，实际上要考的是链表操作和大数思想的结合。如果依赖 BigInteger，你等于放弃了链表这个考点。所以我建议，不管在面试还是平时练习里，都老老实实用逐位相加的方式实现。
5.4 当“一位”变成一个节点之外的复杂对象
工程上还有一种扩展思路：如果链表节点存储的不是一位数字，而是一块很大的数据，比如一个 BigDecimal 片段，那么逐位相加的模型就需要改成“分块相加”，进位也不再只是0或1。这时循环体里的 sum % 10 和 sum / 10 要换成通用的分块进位逻辑。这个扩展能帮你在面试中展示建模能力：你能把一个固定题目抽象成更通用的模式，而不是死记标准答案。
6. 我在真实刷题中踩过的坑（含错误代码复盘）
6.1 常见的错误版本：漏掉最后进位
我先给你看一个看似逻辑很完整、但会翻车的写法：
java复制public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int carry = 0;
while (l1 != null || l2 != null) {
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
cur.next = new ListNode(sum % 10);
carry = sum / 10;
cur = cur.next;
}
return dummy.next;
}
这段代码在绝大多数场景下都能通过，唯独 9->9->9 加 1 会出问题。原因就是循环结束后 carry 为1，但代码没有把它变成新节点。这个错误我在指导别人时见过非常多次。尤其是当你把 l1 和 l2 的移动放在取数之后，循环结束后你根本不会去检查 carry。我后来给自己定了一条规矩：凡是涉及逐位进位的循环，循环结束必须检查进位变量。
6.2 另一种错误：试图把进位直接加到下一个节点上
还有人会这样写：遇到 sum >= 10，就给 l1.next 或 l2.next 的值加1。这个思路听起来像是“先改变下一次输入”，但问题在于：
- 下一次到底读取
l1.next还是l2.next是不确定的，可能其中一条链表已经为null； - 如果两个链表都是
null，最大值应该是19，确实需要一个新节点，但这时还没有节点可以让你加1； - 修改原有节点的值会破坏输入数据，后续调试会变得很混乱。
所以“进位”不应该提前写到链表节点里，而应该作为循环体的一个状态变量传给下一轮。这是我反复强调的一点：进位是计算过程中的状态，不是链表本身的数据。
6.3 我总结的五个自查点
这道题写完之后，我习惯用下面五个点快速自查，五分钟之内能验证大部分边界问题：
- 两个链表长度都为1的情况，比如
5和5，结果是0->1； - 一个链表为空的情况，虽然题目保证非空，但写代码时要能处理；
- 两个链表长度差很大，比如一个1位，一个100位；
- 存在连续多次进位，比如
999和1； - 所有位都相加后恰好产生新的一位，比如
999和0不会进位，但999和1会。
做完这些自查，基本可以放心提交。如果平台返回的超时或错误，也建议先手动打印每个位置的 sum 和 carry，用几个小用例跑一遍，很快就能定位到底哪一位出了问题。
6.4 最后再分享一点个人体会
我在实际刷题和模拟面试里有一个很深的感受：这道题的正确率和工作年限没有必然关系。见过工作多年的老手因为大意漏掉 carry，也见过大二学生把虚拟头节点用得很熟练。差别不在于背不背得下来代码，而在于有没有把每一步的语义想清楚。如果你能闭上眼睛，把输入 2->4->3 和 5->6->4 从第一轮到最后一轮完整走一遍，把 dummy、cur、carry 的变化都说得明明白白，这道题才算真正吃透了。以后遇到任何和逐位运算相关的链表题，比如二进制链表相加、字符串大数相加，你都能用同一套思路很快迁移过去。