1. 题目到底在考什么别被“两数相加”四个字骗了先给刚准备刷LeetCode的朋友说句实在话如果你以为hot100里的“两数相加”Add Two Numbers只是把两个数字加一加那这道题大概率会给你一个下马威。它真正考的从来不是“加法”本身而是三个基本功的叠加——链表遍历、进位处理、边界条件控制。这三样东西几乎是所有链表类题目的共同地基所以你会在LeetCode hot100里反复看到它的身影面试考频也一直稳居高位。这题的原题长这样给你两个非空链表每个链表表示一个非负整数数字按逆序存储每个节点只存一位数字。比如数字 342 会被存成 2 - 4 - 3。你要返回一个新的链表表示两数相加的结果也是逆序存储。换句话说342 465 807返回链表就是 7 - 0 - 8。很多人第一眼看到“逆序”会懵一下为什么好好的正序不用非要倒着存这里有个非常实际的原因——逆序正好对齐了加法从低位向高位进位的过程。你手算加法时是从个位开始加遇到满十就进一位而链表的头节点恰好就是个位所以从头遍历这两个链表跟在纸上列竖式是完全一致的逻辑。这种设计不是故意为难你而是让“进位”这个动作能顺着链表方向自然流动。那它适合谁来刷我的建议是所有准备技术面试的人都应该把它作为链表模块的第一道题来做。原因有三。第一它不依赖任何高级数据结构只需要理解链表节点的基本操作第二它要求你处理“长度不一样的链表”和“最终多出一个进位”这类边界情况这些恰恰是面试官最爱追问的点第三完成这道题之后你会发现后面很多链表题——合并链表、两两交换节点、反转链表——都共享同一套“虚拟头节点 遍历 指针移动”的思维模式。对整个hot100刷题路径来说这道题是典型的“三天入门一周吃透”的胃疼题。入门很容易照着题解敲一遍就能过吃透却需要你把每一步为什么这么做琢磨明白。接下来我就按自己的刷题心得把这道题从思路到实现再到坑点完整拆一遍。2. 官方套路之外的底层思路为什么迭代法是最优解2.1 三种解法选型数组辅助、递归、迭代先把这个题所有可能的路子都摆出来你再决定学哪个。第一种转成数字直接算。把链表变成整数相加后再转回链表。思路听着简单但有一个致命问题——如果链表有几百位语言内置的整数类型根本存不下直接溢出。这道题虽然测试用例长度不会特别夸张但面试官稍微追问一句“如果链表有一万位呢”这个方案就当场破产。所以我不推荐把它作为标准答案但它倒是能帮你理解为什么需要按位相加。第二种递归。递归的写法很简洁本质上还是逐位相加只是用函数调用栈管理遍历顺序。递归的优点是代码短但缺点是如果链表很长递归深度会带来栈溢出的风险而且对初学者来说递归的返回值和进位传递不如迭代直观。它能过题但作为首选手写方案我不太推荐。第三种迭代 虚拟头节点。这是绝大多数题解采用的方案也是我最推崇的做法。它用一个dummy head占位避免处理“第一个节点是否为空的特殊情况”用一个变量carry记录进位循环里同时推进两个链表。整个逻辑完全贴合手算加法的过程空间复杂度只需要 O(1)不算输出链表占用的空间时间复杂度 O(max(m, n))已经是理论最优。为什么迭代法是更优的核心就在可读性和稳定性上。面试时你需要在白板上把代码写清楚、把逻辑讲明白迭代法每一步都能对应到“个位相加、满十进一”的具象操作面试官跟着你的思路走不会累。如果一上来写递归光是解释“为什么递归返回时要带上进位”就要多花两分钟还容易在细节上被追问卡住。2.2 虚拟头节点到底解决什么问题很多初学者第一次看到dummy head会想这不多此一举吗我直接ListNode result null然后一个个拼不就行了我可以负责任地告诉你直接拼确实也能做但代码会丑很多。因为每添加一个新节点你都要先判断“这是不是第一个节点”。如果是你得把result指向它如果不是你才能直接接在尾节点后面。这意味着循环里多一个 if 分支而且稍不留神就会漏掉初始化逻辑出bug的概率直线上升。虚拟头节点的做法是在真正的头节点之前先占一个位置ListNode dummy new ListNode(0); ListNode current dummy;之后你在循环里不断current.next newNode; current current.next;完全不用考虑“第一个节点哪里来”的问题。循环结束时结果链表的头节点就是dummy.next。这个概念极其实用它解决了链表常见的一个痛点头节点常常是一个“特殊情况”最好能用一种统一的方式处理它。你后面刷“合并两个有序链表”“删除链表倒数第N个节点”的时候会发现同样的技巧到处都在用。所以两数相加这道题表面上练的是加法实际上也在练这个贯穿所有链表题的通法。2.3 进位变量 carry整个算法的灵魂无论你是用迭代还是递归carry 都是整道题绕不开的核心。它的逻辑很直白两个节点上的数字相加加上上一次的进位得到的结果如果大于等于10就产生新的进位。但直白归直白写起来有细节。我强烈建议你在循环的每一步都执行同一套公式不要根据“有没有产生进位”去走不同分支int sum (p1 ! null ? p1.val : 0) (p2 ! null ? p2.val : 0) carry; carry sum / 10; int digit sum % 10;注意这里我用了一个很重要的习惯当某个链表已经走到头了就用0补齐。这样两个链表就能用同一个循环处理完不用单独再去写“其中一个链表更长”的尾部追加逻辑。至于为什么用/和%而不是 if 判断纯粹是代码更整齐、语义更清晰。两个一位数加进位最多是 9 9 1 19所以 carry 只会是0或1用除法天然能处理。3. 一步步手写迭代解法从伪代码到完整实现3.1 Java 版完整代码与逐行解读先直接上我最常用的 Java 实现这段代码我在面试现场手写过很多次稳定可靠public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode current dummy; int carry 0; while (l1 ! null || l2 ! null || carry ! 0) { int val1 (l1 ! null) ? l1.val : 0; int val2 (l2 ! null) ? l2.val : 0; int sum val1 val2 carry; carry sum / 10; current.next new ListNode(sum % 10); current current.next; if (l1 ! null) l1 l1.next; if (l2 ! null) l2 l2.next; } return dummy.next; }注意一个细节我的循环条件是l1 ! null || l2 ! null || carry ! 0把carry 也放进循环条件里了。这是很多第一次写这道题的人会忽略的点——如果两个链表都遍历完了但最后一次相加产生了进位你没有把这个进位加进去结果链表的长度就会少一位。比如 5 5 10最终链表应该是0 - 1如果你循环提前结束就只剩下0直接错。这个“carry 也参与循环判断”的习惯我建议你直接刻进肌肉记忆里。逐行看这段代码的逻辑第1行到第3行建立虚拟头节点dummy和游标指针current初始化carry 0。第5行的 while 条件是核心它保证“两个链表有任何一个没走完”或者“还有进位没处理”时循环都要继续。第6行到第8行取出当前节点值如果链表已经空了按0处理。这里有一个隐藏保证sum的最大值就是9 9 1 19所以carry只能是0或1不需要考虑更大的进位。第10行到第12行生成新节点并挂到结果链表尾部同时移动游标。第13行到第14行两个链表指针各自向后移动。这里注意千万不要在l1 ! null之前盲写l1 l1.next否则链表走到空指针时会直接报NullPointerException。最后返回dummy.next把虚拟头节点丢掉暴露真正的链头。我经常跟朋友说这段代码“短小精悍但五脏俱全”它把链表题最常踩的坑全踩了一遍又全填了——空指针、进位丢失、虚拟头节点。把它背下来不算本事能把每一步为什么这么写讲清楚才算吃透。3.2 Python 版与 Go 版多语言对比学得更透如果你用 Python代码结构几乎完全一样class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(0) cur dummy carry 0 while l1 or l2 or carry: v1 l1.val if l1 else 0 v2 l2.val if l2 else 0 total v1 v2 carry carry total // 10 cur.next ListNode(total % 10) cur cur.next if l1: l1 l1.next if l2: l2 l2.next return dummy.nextPython 的三元表达式和 Java 略有差异但核心逻辑一模一样。这里提醒一下 Python 选手如果你在本地写完想跑测试记得自己先定义一个ListNode类LeetCode 的在线环境会帮你处理但本地环境可不会。Go 版本我也顺手贴一下因为现在不少后端岗位面试允许用 Gofunc addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { dummy : ListNode{} cur : dummy carry : 0 for l1 ! nil || l2 ! nil || carry 0 { v1, v2 : 0, 0 if l1 ! nil { v1 l1.Val l1 l1.Next } if l2 ! nil { v2 l2.Val l2 l2.Next } sum : v1 v2 carry carry sum / 10 cur.Next ListNode{Val: sum % 10} cur cur.Next } return dummy.Next }多语言对比的最大意义在哪你会发现解法完全由数据结构和算法决定和具体语法关系不大。你把一种语言的写法吃透了迁移到其他语言就是改个声明和语法符号的事。这也是我刷题一直坚持的习惯一道题至少看两种语言的官方题解不为别的就是为了把“思路层”和“语法层”分开理解。3.3 链表节点定义与几种场景推演在 LeetCode 里链表节点的定义默认是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没有前驱指针。这也意味着我们只能单向移动没法回头所以“先遍历完两条链表再倒序处理”的方案天然不适用于这种结构。为了帮你彻底理解循环过程我手动推演两个场景。场景一最简单的同长度进位。l1 2 - 4 - 3l2 5 - 6 - 4。第一位2 5 0 7carry 0结果节点为 7第二位4 6 0 10carry 1结果节点为 0第三位3 4 1 8carry 0结果节点为 8链表走完carry 0结束返回结果7 - 0 - 8对应 342 465 807正确场景二长度不同且最高位有进位。l1 9 - 9代表99l2 1代表1。第一位9 1 0 10carry 1结果节点为 0第二位9l1的第二个节点 0l2已经为空补0 1 10carry 1结果节点为 0循环判断l1、l2都为空了但 carry 1继续第三位0 0 1 1carry 0结果节点为 1返回结果0 - 0 - 1对应 99 1 100正确注意场景二里最关键的地方第二个节点加完后两个链表其实都已经走完了但因为 carry 还有值循环必须再执行一次才能把最高位的进位输出成新节点。这就是我在代码里把carry ! 0写进循环条件的原因。3.4 时间复杂度与空间复杂度分析这个题的复杂度分析是面试必问的我建议直接用标准的表述背下来但更重要的是理解它怎么来的。假设 l1 的长度是 ml2 的长度是 n。时间复杂度O(max(m, n))。因为循环每轮消耗两个链表各一个节点最多执行到较长的那条链表结束。再加上可能多出一轮处理最后的进位所以严格的写法是 O(max(m, n) 1)但在大 O 表示法里常数和加1都被忽略了最终写 O(max(m, n)) 即可。空间复杂度O(max(m, n))。这里要解释清楚题目要求返回一个新的链表新链表的长度大致是 max(m, n) 或 max(m, n) 1取决于是否有额外进位这个空间是“输出本身”占用的。如果银行的面试官问“额外空间”你要回答除了输出链表之外我们只用了常数个指针变量dummy、current、carry等所以额外空间复杂度是 O(1)。别小看这个“额外空间”和“总空间”的区分在阿里、字节这类喜欢深挖的公司面试官可能就盯着这一点来考察你到底是背了答案还是真明白。我见过不少候选人能把代码写对但一问空间复杂度就笼统回答“O(n)”被追问“这个n是什么、为什么不是O(1)”就卡壳了。4. 刷题过程中最常见的几个坑与排查技巧4.1 链表长度不一致时千万别让指针脱空新手最容易翻车的就是这里——两个链表长度不等短的已经走完了你还在循环里取l2.val直接空指针异常。解决方法就是我前面用的“补0”策略每次取节点值时先判断链表是否为 null如果是就取0而不是去访问它的.val属性。这个习惯并不仅限于这道题你以后处理“合并两个有序链表”“两个字符串相加”等所有“需要对齐两个序列”的题目时都会用到。还有一个细节取完值之后移动指针的代码也必须有判空保护。有些同学会在循环开头写了判空但忘了在循环末尾移动指针时再判断一次导致空指针。我在自己的 Python 版本里直接写if l1: l1 l1.next if l2: l2 l2.next用if包一层永远安全。这个写法看起来有点啰嗦但它能省掉你在调试器里耗掉的10分钟。4.2 最高位进位的丢失问题这个问题我在话题热度里看到很多人在问“两个链表都遍历完了结果却少了一位。”我给你一个经典例子l1 9 - 9l2 1按刚才的推演正确结果是0 - 0 - 1但如果你用下面这种“偷懒”的循环条件while (l1 ! null || l2 ! null) { ... }那么遍历完9 - 9和1之后循环直接退出最后一个进位 1 压根没进入结果链表。你得到的结果是0 - 0表示 0而正确答案是 100这错得相当离谱。排查这种问题的方法我习惯在循环结束后单独打印一下carry的值System.out.println(carry at end carry);如果你看到 carry 是1但你脑子里的期望结果还有下一位那一定是循环条件写漏了。修复方式就是前面反复强调的把carry ! 0加进循环条件或者是在循环结束后补一段处理尾部进位的代码。4.3 面向面试的边界用例自测清单我在刷题和模拟面试中总结了一套专门给“两数相加”用的测试用例清单。写完代码先别提交自己拿这几组用例在脑中或本地跑一遍两个链表长度相同且无进位1 - 23 - 44 - 6两个链表长度相同且中间有连续进位5 - 65 - 60 - 3 - 1注意最高位多了一位两个链表长度不同1 - 2 - 34 - 55 - 7 - 3其中一个链表只有一个节点910 - 1其中一个是空链表如果题意允许的话空 1 - 21 - 2全9加全99 - 9 - 910 - 0 - 0 - 1这套清单也是我在 LeetCode 讨论区看到大家反复踩坑总结出来的。你把这6个用例跑通了这道题的正确性基本就有保证了。面试的时候把这些用例主动讲给面试官听会明显显得你“有工程意识”比闷头写代码得分更高。4.4 一个经常被忽略的工程细节不要修改输入链表有些学生会写出这样的代码while (l1 ! null || l2 ! null || carry ! 0) { if (l1 ! null) { l1.val (l2 ! null ? l2.val : 0) carry; ... } }能够通过题目但副作用是它会修改输入的 l1 链表。在 LeetCode 上这通常不报错因为测试用例不会复用它但在真实工程环境中调用方往往还要继续使用传入的数据你把人家的链表改了就是严重的 bug。所以我在代码里始终坚持“只读输入、新建输出”的原则。这也是工程经验对算法题的一种反向塑造刷题不只是为了通过判题机更是为了养成良好的代码习惯。如果你在面试时说一句“这里我用的是新建链表不会修改原始的 l1 和 l2”我相信面试官对你的评价会自动高一个档次。5. 从两数相加出发hot100中的变体题与思维迁移5.1 变体一如果链表不是逆序存储而是正序存储这是最常见的追问。如果数字按正序存储比如 342 存成3 - 4 - 2而加法需要从低位开始你就要先想办法让链表“反”过来。最直观的方案有两个。第一种反转两条链表然后复用这道题的解法最后再把结果反转回来。第二种用栈把两条链表的值全部压入栈中弹栈的顺序天然就是逆序然后按位相加。两者都能解决复杂度也都在 O(max(m,n)) 级别。面试官让你选一个我建议你优先说“反转链表”因为它对空间更友好栈需要额外 O(max(m,n)) 空间反转链表可以做到额外 O(1)。这个变体让“两数相加”的思维导图瞬间扩展了你不仅要会加还要熟练“反转链表”和“栈”这两个基础操作。hot100里 “反转链表” 本身就是一道独立题目所以这一问其实是在考察你对邻近题目的串联能力。5.2 变体二换成字符串/数组又该怎么写LeetCode 上还有一道类似的题叫“字符串相加”题目编号是 415给定的输入是两个数字字符串把它俩相加并返回字符串。核心思路和这道题一模一样从右往左即从低位到高位遍历字符串维护 carry每次用digit1 digit2 carry算结果最后不要忘了翻转。数组版本更简单直接把链表换成数组连“.next”都不用管用下标从后往前遍历就行。为什么要提这些变体因为在真实的面试场景里面试官很少直接给你原题你大概率会见到它的换皮版本。如果你能一眼看穿“换皮不换核”这道题的复习价值就真正内化成你自己的能力了。5.3 借鉴大整数运算思想这个算法能用在业务里吗学习算法最容易陷入误区的问题是“这玩意除了面试还有什么用”但“两数相加”背后的思想在真实业务场景里其实非常常见。想象一个场景你在做一个银行系统需要支持超大金额的跨系统对账数据库里存量金额是用字符串存储的几十位数字超过64位整数范围。你要对两个这样的字符串做加法并且保证不丢精度怎么办随便把字符串解析成 double 算精度立刻崩了。正确的做法就是像这道题一样逐位相加维护进位。很多语言的原生 BigInt 底层就是这样实现的。再比如你在做网络协议解析数据包里的数值字段可能是定长的BCD编码二进制编码的十进制数在硬件层面做校验和计算的本质同样是逐字节相加再进位。算法题抽象出来的思路落回真实的数字系统万变不离其宗。这也是我为什么一直觉得不要用“背题”的心态去刷 hot100要用“建立思维模式”的心态去刷。5.4 怎么把这道题融入你自己的刷题计划关于 hot100 怎么刷网上有一堆方法论但我想给你一个比较实际的落地方案。把“两数相加”放在链表专题的第一天去做和它排在同一天的最佳搭档是“反转链表”和“合并两个有序链表”。这三道题可以共用同一套解题模板虚拟头节点 while 循环 指针移动。第一天先看题解照着敲一遍可以但一定要给自己留出“第二天白板重写”的复习安排。第二天不看任何参考凭记忆手写再把自己卡住的地方标记出来那些卡点正是你没吃透的地方值得写进笔记。然后到周末可以顺便做一下“字符串相乘”LeetCode 43因为它需要你先把“两数相加”理解透才能处理中间结果。这样一来一个知识点串起了三到四道 hot100 题目你的刷题效率比“一天刷十道但互不关联”要高得多。6. 面试时怎么说表达这门手艺也值得练代码写对只是第一步面试时怎么把自己的思路清晰地表达出来是很多人忽略的第二关。我经常在模拟面试里提醒候选人沉默地写完代码和边写边讲在面试官眼里完全是两个人。一个比较稳妥的表达节奏是这样的先说思路“这题本质是按位相加类似于手算加法我用一个虚拟头节点保存结果用一个 carry 变量保存进位循环条件要覆盖两个链表未耗尽或 carry 非零的情况。”再补复杂度“时间上是 O(max(m,n))因为每个节点最多访问一次额外空间是 O(1)因为只用到了几个指针。”最后主动提边界“需要注意当一个链表提前结束时补0处理以及遍历完后如果 carry 还有值要额外创建一个新节点。”这三个步骤说完面试官基本能确认你是真的理解了而不是背题。我还会建议你把“为什么用虚拟头节点”也主动讲一下“这样避免了第一个节点需要单独初始化的麻烦代码更统一。”这一句话在面试里很加分因为它表明你有工程意识不只是会对着题解抄。另外如果你在面试中被要求“用递归写一下”也不要慌。递归的思路是把当前的节点值相加处理进位然后递归处理下一组节点。你可以说“迭代更符合这道题直观的加法过程递归也可以但需要注意链表较长时栈溢出风险”这种比较式的回答会让面试官觉得你有全面的理解。7. 再聊一个我自己踩过的坑关于本地调试的思路刷题刷到后面你会发现很多题在 LeetCode 在线编辑器里跑得贼快但一放到本地 IDE 就各种报错。原因往往是 LeetCode 帮你自动处理了链表的输入输出而本地环境没有这些脚手架。两数相加是我第一次认真写本地测试用例的题当时花了不少时间踩坑这里把一套简单的本地验证思路分享给你。核心是两步第一步自己写一个链表构造方法把数组转成链表第二步自己写一个打印方法把链表输出成数组或字符串。下面是 Java 的示例// 数组转链表 private static ListNode buildList(int[] nums) { ListNode dummy new ListNode(0); ListNode cur dummy; for (int num : nums) { cur.next new ListNode(num); cur cur.next; } return dummy.next; } // 链表输出为字符串 private static String listToString(ListNode head) { StringBuilder sb new StringBuilder(); while (head ! null) { sb.append(head.val); if (head.next ! null) sb.append( - ); head head.next; } return sb.toString(); }然后你在main里跑ListNode l1 buildList(new int[]{2, 4, 3}); ListNode l2 buildList(new int[]{5, 6, 4}); ListNode result new Solution().addTwoNumbers(l1, l2); System.out.println(listToString(result)); // 期望输出 7 - 0 - 8这套代码虽然简单但它是你以后调试所有链表题的通用工具值得存成一个本地文件反复使用。我自己的习惯是把所有链表公共方法放到一个LinkedListUtils类里后期刷“反转链表”“合并K个有序链表”都能直接复用。还有一个小技巧如果提交后返回了 “Time Limit Exceeded” 或 “Runtime Error”先把用例缩小到最小复现。比如把链表长度缩到 1~2 个节点加上打印语句肉眼就能看出问题。很多时候问题只是cur cur.next少写了或者循环里l1和l2的判空写错了。我自己刚开始刷这道题的时候也曾经在“反转之后忘了反转回来”这种愚蠢错误上浪费过一整个晚上。后来养成了“写完代码先在脑中跑一遍小用例再提交”的习惯通过率提升了很多。这个习惯才是刷题真正带给我的东西。