1. 题目拆解为什么“两数相加”能进hot100第一次在力扣hot100里刷到“两数相加”这道题很多人会觉得它太基础了——不就是个链表遍历吗但真把它放在hot100这个位置面试里出现的频率又高得离谱背后是有原因的。这道题表面考的是链表操作实际考察的是三个层面的东西对链表这种数据结构的熟悉程度、对进位机制这种“状态传递”问题的处理习惯以及面对边界条件时能不能想全。题目描述本身不复杂给你两个非空的链表每个节点存一位数字数字按照逆序存储也就是说链表的头节点对应数字的个位。你要把两个数相加返回一个新的链表同样按逆序存储。比如左边链表是2-4-3右边是5-6-4对应的数字是342和465加起来是807逆序输出就是7-0-8。这里有个很多新手会忽略的点为什么题目要把数字逆序存储这其实就是出题人在降低难度。因为我们平时做加法就是从个位开始加从个位向高位进位。链表如果正序存储我们还得先遍历到尾部才能开始加或者借助栈、反转链表来辅助而逆序存储意味着链表头就是加法的起点你可以一边遍历一边计算天然适合单向链表。适合来研究这道题的人我觉得有三类第一类是刚开始刷链表题的新手这道题是链表遍历的“敲门砖”做好了后续的“合并两个有序链表”“删除链表的倒数第N个节点”都会顺手很多第二类是要准备面试的同学这道题在各大厂的算法面试里属于“热身题”级别但答得好不好面试官一眼就能看出你的代码习惯第三类是已经刷过一遍但想整理解题框架的人把这道题吃透往后遇到“两数相加II”“字符串相加”“二进制求和”这类同族题目你会发现自己能很快迁移过去。这道题的核心价值不在于“会做”而在于你能不能把加法运算本身蕴含的“进位”逻辑用代码表达得干净、严谨、无遗漏。接下来我从思路、实现、坑点、扩展四个维度把这道题聊透。2. 核心思路从“竖式加法”到“链表遍历”的映射2.1 竖式加法背后的状态机思维你先回忆一下小学学的竖式加法。两个数从个位开始对齐每一位上的两个数字相加如果结果大于等于10就把十位的1进到更高一位当前位只保留个位数部分。这个过程中有两个关键点一个是对齐一个是进位。对应到这道题链表的逆序存储已经帮我们解决了“对齐”问题——两个链表的当前节点天然就是同一个数位。剩下的核心就是“进位”怎么处理。我习惯把进位理解成一个“状态变量”每一轮计算时当前位的和等于链表A的节点值、链表B的节点值、以及上一轮产生的进位三者相加。然后当前位要存进结果链表的值是总和模10而新的进位是总和除以10向下取整。sum valA valB carry node.val sum % 10 carry sum / 10这三个公式就是这道题的“题眼”。只要把这个逻辑写清楚算法主体就完成一大半了。很多解法看起来代码不一样但本质都是在维护这三个量。2.2 哑节点链表题里最实用的“占位术”在实际写代码时我们要构造一个新的链表来存放结果。这里就涉及一个常见的实现细节问题链表是从头开始逐个往后挂节点的但最终要返回的是头节点。如果直接在循环里new节点你得额外用一个变量记住头节点是谁否则等循环结束就找不到了。这个问题有一个非常标准的解法哑节点dummy node。先创建一个不存实际数值的节点作为占位然后让一个游标指针从哑节点开始往后串。循环结束后返回dummy.next就是真正的头节点。这样做的核心好处是你永远不需要在循环里判断“当前是不是第一个节点”也就不需要单独处理头节点的特殊情况。ListNode dummy new ListNode(0); ListNode cur dummy; // 循环里不断 new 节点挂到 cur.next然后 cur cur.next return dummy.next;我见过不少新手不喜欢用哑节点觉得多此一举。但等他们写几遍之后就会发现用哑节点让代码的边界分支至少少了一半。为什么很多教科书和题解都推荐这个写法因为它把“头节点是否为空”这个判断从每次循环里抽离出去了逻辑上更统一。2.3 循环条件两个链表都为空不等于循环结束这是这道题最容易踩的坑之一。很多初版代码会这么写while (l1 ! null l2 ! null) { // 计算当前位 }这个写法在l1和l2等长时没问题但只要有一个链表先走完循环提前退出剩余的部分就没处理。有人会想那我循环结束之后再把长链表剩下的节点接上去不就行了可以但你漏了一个致命场景——进位可能一直传递下去。举个经典例子999 1。如果用逆序链表表示左边是9-9-9右边是1。个位加起来是10进位1十位9加进位1又是10再进位1百位8假设是999那就是9加进位1又是10又进位1。最后还得额外new一个节点存最后的1结果才能变成1000。如果你在某个链表遍历完后直接“接上剩余节点”这个连续性进位就丢了。所以正确的循环条件应该是while (l1 ! null || l2 ! null || carry ! 0) { // 只要还有节点可遍历或者进位不为0就得继续 }2.4 时间复杂度与空间复杂度这道题的“成本账”在算法题里写完代码之后一定要能说清楚复杂度的量级。这道题的时间复杂度是O(max(m, n))m和n分别是两个链表的长度。因为无论两个链表哪个更长我们最多遍历完较长的那条链每个节点访问一次总操作次数和较长链表的长度线性相关。空间复杂度这块就要注意了如果你不计输出链表占用的空间那额外使用的变量只有常数个空间复杂度是O(1)。但如果你把新建的链表也算进去那么结果链表最长是max(m, n)1多出来的1是最后一次进位产生的空间复杂度就是O(max(m, n))。面试时我建议你主动说明这一点直接把两种口径都讲出来会显得你对空间的概念很清晰。3. 完整实现从零手写一遍注意这些细节3.1 Java版本面试场上最常用的写法Java是很多公司面试的主语言所以我先把Java版本贴出来。这段代码我尽量保持“最优美且好记”的形态方便你直接背诵框架class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode cur dummy; int carry 0; while (l1 ! null || l2 ! null || carry ! 0) { 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); cur cur.next; carry sum / 10; } return dummy.next; } }这段代码有几个细节值得展开讲首先我把sum的初始值设成了carry这样就不用单独再写一次sum carry代码更紧凑。其次我在判断l1、l2是否为null之后立即把指针移到下一个节点这样一来循环体里不会出现“空指针下一跳”的隐患。最后carry sum / 10放在循环末尾因为进位一定是在算完当前位之后才产生的顺序不能反。3.2 Python版本更贴近伪代码的写法如果你用Python刷题代码会更短一点但逻辑完全一致class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(0) cur dummy carry 0 while l1 or l2 or carry: total carry if l1: total l1.val l1 l1.next if l2: total l2.val l2 l2.next cur.next ListNode(total % 10) cur cur.next carry total // 10 return dummy.nextPython版本里while的条件直接写l1 or l2 or carry简洁且直观。这里有个小知识carry是整数在Python里0为假非0为真所以or carry在carry为0时自动退出循环不用额外写carry ! 0。3.3 逐步模拟拿一个刁钻用例走一遍光看代码可能还是不够直观我带你把一个容易出错的用例完整走一遍l1 9-9-9l2 1。初始dummy(0)cur指向dummycarry0第一轮sum09110新节点值为0carry1l1移到第二个9l2变为null第二轮sum19010新节点值为0carry1l1移到第三个9l2仍为null第三轮sum19010新节点值为0carry1l1变为nulll2为null第四轮虽然l1和l2都为null但carry1不为0进入循环sum1001新节点值为1carry0循环结束结果是0-0-0-1即1000和预期一致注意第三步结束之后还不能停因为carry还等于1。这个场景就是前文说的“连续进位”的典型表现。如果你在循环里没考虑到carry ! 0返回的结果就会变成0-0-0少了最高位结果差之千里。3.4 一个面试加分项原地修改长链表如果你想在面试里展示得更深入一点可以提另外一种思路不新建链表而是选择两个链表中较长的那个把结果直接覆盖到长链表上。这样空间复杂度可以压到真正的O(1)。大致的思路是先遍历一遍两个链表统计长度确认谁更长。从短链表头开始把对应节点值累加到长链表对应节点上同时维护进位。短链表走完后继续单独处理长链表剩余部分把进位一路传递下去。最后如果长链表尾部的进位不为0再new一个新节点挂在末尾。这种写法代码会复杂一些而且面试时容易出错但如果答得干净利落面试官会认为你对链表的掌控力不错。日常刷题时可以练一练这个思路不过不建议在限时笔试中冒险毕竟新建链表版本已经足够清晰可靠。4. 常见问题与排查技巧实录4.1 高频报错对照速查表我把刷这道题时大家最容易遇到的报错和问题整理成了一个表格方便你对着排查症状原因解决办法结果丢了一个最高位节点while循环条件漏掉carry ! 0改成while (l1 ! null || l2 ! null || carry ! 0)空指针异常在l1或l2为null时仍访问了.val进入循环后先判断是否为null再取值返回结果为空或null直接返回了cur而不是dummy.next结果链表一定要通过dummy.next拿到头节点结果链表顺序相反误把节点插到了链表头部使用cur.next new ListNode(...)然后cur cur.next顺序后移代码在l1/l2不等长时出错只用一个while循环且条件为循环条件改为||并在体内对null做判空4.2 最容易忽略的“尾进位”场景这道题在LeetCode的测试用例里有一个专门考验你的用例l1 9-9-9-9-9-9-9l2 9-9-9-9。也就是9999999 9999 10009998。你会发现在短链表遍历完后长链表还有好几级而且更重要的是长链表的高位部分可能直接被最后的进位数“污染”。很多人在短链表结束后直接break或者在l1为null时直接把l2剩余的节点接入结果链表这其实隐藏了一个bug如果当前进位是1而l2剩余部分的第一个节点值是9那么9110应该再产生进位并且当前节点应该存0。直接“接上原链表”等于把进位丢掉了。正确的做法是即使某一个链表变成null循环也要继续直到另一个链表也为null且进位为0为止。你可以在草稿纸上画一下这个用例的状态变化跑一遍就再也不会忘。4.3 大数据用例下的溢出问题如果你把两个链表的数字先转成整数再相加那你一定会踩到一个坑整数溢出。比如链表长度是20每个节点都是9那对应的数字是20位的999...9早把int和long的空间都超出了。这道题给的是链表而不是字符串本质上就是在提示你“不要试图把数字还原出来”。所以正确的姿势一定是“逐位相加边加边进位”。这也是这类“大数相加”类题目的核心思想——用数据结构存储大数的每一位再用人工竖式的方式逐位运算从而规避编程语言数值类型的上限。理解这一点你就不难理解为什么会有“两数相加II”“字符串相加”“二进制求和”这些同族题目了它们的思路完全一致。4.4 关于测试用例的自测建议很多人提交通过就不管了但我建议你至少用这几组用例自测一下两个链表都是单节点且无进位[2] [3] - [5]个位产生进位[5] [5] - [0, 1]长度不等[1, 8] [0] - [1, 8]连续进位且产生新最高位[9, 9, 9] [1] - [0, 0, 0, 1]一个链表为null题目声明非空但自己测试时可以试试边界把这些用例在你的代码里跑一遍尤其是第四种。如果第四种能过你的进位逻辑基本就没问题了。5. 同族题目扩展一道题吃透一类题5.1 同族题目的迁移路径把这道题吃透之后你可以顺手把这一批题目刷掉它们本质上共享同一套“大数相加”框架题目差异点应对策略力扣445题两数相加II链表正序存储数字先反转两个链表变成逆序再复用本题逻辑力扣67题二进制求和输入是字符串逢二进一从末尾逐位相加carry除以2结果模2力扣415题字符串相加输入是十进制的字符串从末尾逐位相加carry除以10结果模10力扣43题字符串相乘大数乘法需要双层循环先逐位相乘累加到一个数组再统一处理进位你会发现这些题的核心都是sum a b carry只是进位制不同、存储方式不同。当你把一个进位逻辑彻底想明白其他题就只是改几个常数的区别。5.2 链表的反转操作相邻题目的必备技能如果是正序存储的“两数相加II”它的解法是把两个链表先反转然后复用本题代码最后把结果再反转回来。这里反转链表本身也是一道经典题。我推荐你练一下迭代式反转记住三行核心逻辑ListNode prev null; ListNode cur head; while (cur ! null) { ListNode nextTemp cur.next; cur.next prev; prev cur; cur nextTemp; }这组代码的精髓在于先用一个临时变量保存当前节点的下一个节点再把当前节点的next指向前一个节点接着整体向后移动。很多链表题比如判断回文链表、反转链表II都会用到它建议顺手练熟。5.3 从题目到工程什么场景会用到这种写法你可能会好奇实际工程里谁会真的用链表存大数相加其实这个概念在底层计算里非常常见比如CPU里的加法器就是通过逐位相加并传递进位来实现二进制加法的又比如在实现高精度计算库、处理超长整数超过64位时我们也会用数组或链表来模拟竖式加法。另外在一些分布式系统中数字过大无法用常规类型表示时也会拆成数组逐段存储并分段计算。从这个角度看这道题的价值不止于面试。它训练的是“把连续性操作拆解为状态迭代”的思维这种思维在写状态机、流水线处理、流式计算的时候都会用到。6. 面试现场模拟拿到题后应该怎么思考很多读者刷题时会陷入一个误区看到题目直接写代码写到一半发现漏了边界条件再回去补。这个习惯在面试里很致命因为面试官看重的不只是答案对错还有你的思考过程。我建议你拿到这道题之后按这个顺序来第一步先说思路。告诉面试官这道题的链表是逆序存储相当于个位对齐所以我可以从头到尾同步遍历两个链表用一个变量carry记录进位。循环条件是两个链表都不为空或者进位不为0。第二步解释关键细节。主动说出“我打算用dummy节点这样可以避免处理头节点的特殊情况”。这句话会立刻让面试官觉得你有经验。第三步处理边界条件。自己主动提出来“要注意两个链表长度不同以及最后一位进位的情况”。这个时候面试官通常心里已经在给你加分了。第四步分析复杂度。明确说出时间O(max(m,n))空间O(1)不计返回链表。为什么我一直强调这个顺序因为面试的评分标准里有很大一部分是“沟通与逻辑清晰度”而不仅仅看最终代码能不能跑通。你按上面这个流程走就算中途有小bug面试官也愿意引导你修正反过来如果一声不吭闷头写完细节稍有不慎就会全盘皆输。7. 进阶思考如果要求你不能修改原链表呢原题直接遍历是可逆的因为没有要求你不能修改链表。但有些面试官会追加一个问题如果要求返回的新链表不能依赖原链表节点并且你不能修改原来的两个链表怎么办这个约束意味着你不能把结果直接挂到其中一个链表上必须完全新建节点。其实这恰恰是上面标准解法已经在做的事cur.next new ListNode(sum % 10)本身就是新建节点所以这个追加条件并不影响标准解的正确性。但如果你选用了“原地修改长链表”的做法那这个追加约束就直接把你的方案否了。面试时遇到这种追加约束别慌你只要迅速在脑子里过一遍我的解法是否创建了新节点是否触碰了原链表如果没有就直接回答“我的解法天然满足这个约束”面试官会认可你考虑问题的全面性。这道题我刷过非常多次也看过很多种不同风格的写法。每次重新看我都会感慨好的代码确实是有“呼吸感”的——它不会把所有逻辑堆在一起而是把每个子问题拆得干净利落让读的人能顺着你的思路一路到底。两数相加这道题恰恰就是训练这种“干净利落”的绝佳素材。最后再分享一个我个人的小习惯每次刷完链表题我都会用笔在纸上画一遍节点的指针变化过程不画代码只画箭头。这个过程能帮你把“链表的指针操作”从死记硬背变成真正的空间直觉。坚持一段时间你会发现再做链表题脑子里的那幅图会自动浮现出来。