1. 为什么这道题值得反复刷三遍1.1 题目本身到底在考什么两数相加在力扣上是第2题属于那种看起来特别简单、写起来全是细节的经典题目。题面讲得很直白给你两个非空的链表每个节点存一位数字数字是逆序存储的也就是链表头节点对应的是个位要求把两个数相加返回一个新的链表同样用逆序存储。我第一次刷这道题的时候心想这不就是竖式加法嘛个位对齐、逢十进一小学生都会。结果真上手写代码的时候第一版直接崩了原因是我用了那种先把链表转成数字加完再转回链表的偷懒写法——两个链表各循环一遍拼成整数相加然后再循环取每一位构建新链表。用例一多直接撞上整型溢出。那一刻我才意识到这道题考的根本不是你会不会加法而是你懂不懂链表这种数据结构的操作细节能不能在指针移动、节点创建、边界判断这些琐碎环节里不犯错。力扣把这道题放在链表专题的前几道位置很讲究。它既不像两数之和那样依赖哈希表的巧妙映射也不像反转链表那样只有一个核心动作。两数相加恰好卡在中间算法思路简单到透明工程实现却暗藏七八个容易翻车的点。对刷题新手来说这是一道完美的从看题解到自己写的过渡题对准备面试的人来说这也是面试官最爱拿来试探候选人代码基本功的题目之一因为一个小时内从思路沟通、边界确认到写码调试全部流程都能暴露出来。这道题真正在考察的能力清单在我看来是这几项第一能不能识别出逆序存储这个条件其实是在故意降低难度——个位对齐意味着两个链表的头节点就是低位不用做任何反转预处理第二能不能意识到直接用整数运算会溢出从而第一时间抛弃转数字再相加的路径第三能不能在链表的循环中同时处理两个不同长度的链表、进位标记、以及结果链表尾部可能多出来的节点。这三个能力点恰好对应了链表操作的三大基本功遍历、构造、边界处理。1.2 最容易踩的数值溢出直觉坑先把这个最经典的坑单独拎出来说因为它是区分背过题解和真理解的分水岭。很多人第一次看到这道题的直觉反应是把两个链表里的数字取出来转成 int 或者 long加起来再转回链表。这个思路在小学数学层面完全正确在工程层面却是个定时炸弹。力扣的题目约束里明确写过链表长度范围虽然不同版本的题面措辞会有调整但实战中你大概率会遇到超长链表。Java 的 int 最大约21亿long 最大约922亿亿听起来很大可一旦链表长度超过10位long 就开始吃力超过19位long 直接溢出。力扣的测试用例里出现几十位甚至上百位的数字是常态你辛辛苦苦把链表转成数值结果相加的一瞬间数据就错了然后你还得花大量时间排查我明明加了为什么结果不对。更隐蔽的问题是即使语言支持高精度数值比如 Python 的 int 无上限这种做法也绕了一个大弯为了算加法你先把链表结构拆散成数值算完又要用取模和整除把它重新组装成链表时空效率都很亏。而且这种写法完全丢失了这道题想考察的链表操作能力面试官看到这种解法基本会直接判定基础不扎实。正确的思路是模拟竖式加法的手算过程两个指针分别从两个链表头出发每一位上的数字相加再加上上一位的进位结果对10取模得到当前位对10整除得到进位然后两个指针同时后移。这个过程不需要把任何数据转成数值天然避开了溢出问题也天然适配了链表的结构。想通这一点这道题的算法骨架就已经在脑子里了。2. 逆序链表的结构拆解与指针细节2.1 链表节点定义与输入数据的真实含义力扣的链表节点定义是经典的单链表结构在代码里通常是这样一个类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; } }Python 版本对应的是class ListNode: def __init__(self, val0, nextNone): self.val val self.next next理解逆序存储这四个字是读懂这道题的前提。以数字 342 为例它对应的链表是 2 - 4 - 3也就是头节点是 2第二个节点是 4尾节点是 3。为什么力扣要设计成逆序从数据结构的角度看这个设计非常聪明两个数字相加是从低位开始的而链表的遍历只能从头部开始逆序存储刚好让最低位和链表的遍历起点重合这样一来你不需要做任何反转操作直接从头开始逐位相加就是正确的计算顺序。这种存储顺序和计算顺序一致的设计在工程里其实很常见。回想一下我们手写竖式加法时习惯上把个位写在最右边从右往左算但计算机遍历链表只能从左往右走所以把个位放在链表头就成了为了遍历方便而调整存储顺序的典型例子。类似的思路在很多大数运算库中也有体现比如某些高精度计算库会把数字按低位在前的方式存储在数组中目的就是让运算循环从下标0开始省去反转操作。实际的输入数据长什么样题目保证两个链表都是非空的每个节点存储的数字范围是 0 到 9。这里有个容易忽略的细节虽然每个节点是一位数但两个链表的长度可以完全不同。比如第一个链表代表 1 - 3 - 5 - 7数字 7531第二个链表代表 9 - 2数字 29两个链表长度分别是4和2。这意味着你的循环条件不能只盯着其中一个链表必须同时考虑两个链表都还有节点或者进位还不为0这三种情况。还有一个隐含信息是两个数本身不会以 0 开头除非这个数本身就是 0。所以你不会遇到链表里存了一大串前导零这种无意义的情况这也简化了边界处理。但非空不等于不会出现 0比如一个链表只有一个节点 val0这种情况是完全合法的你的代码必须能正确处理 0 加上任意数。2.2 虚拟头节点一个让代码简洁一半的惯用法写链表算法题的时候虚拟头节点dummy head可以说是我最依赖的技巧之一两数相加这道题就是个很好的示例。如果不使用虚拟头节点你需要在循环开始前单独处理结果链表的第一个节点先手动计算个位相加的结果创建头节点然后才开始循环处理后续节点。这个特判逻辑会打乱代码的节奏而且增加出错概率。使用虚拟头节点之后你只需要创建一个值为任意占位数的节点作为起点然后循环里统一创建新节点并接在尾节点后面循环结束时直接返回dummy.next头节点的处理被完全抹平了。dummy ListNode(0) # 虚拟头节点最终返回 dummy.next cur dummy # cur 指向当前结果链表的尾节点这段代码一写出来思路立刻就清晰了cur 永远指向结果链表的最后一个节点每次循环算出一位结果就新建一个节点挂在 cur 后面然后 cur 后移。整个过程不需要关心这是第几位是不是第一位逻辑完全统一。这里有个经验之谈在链表的原地操作场景里比如反转链表、删除节点虚拟头节点能省掉大量如果删除的是头节点该怎么办之类的边界讨论。在两数相加这种从零构建新链表的场景里虚拟头节点的作用是统一的节点创建逻辑避免把答案开头和其他位置区别对待。两种场景我都建议大家专门练一练因为虚拟头节点的使用习惯一旦养成几乎所有的链表构造类题目你都能直接套这个模板。3. 完整解法实现从伪代码到可运行代码3.1 核心循环的每一步在做什么从算法思路上说这道题只需要一个 while 循环循环里做四件事取当前位的值、求和、计算当前位和进位、移动指针。我用 Python 写一版最标准的解法配合注释看每一步的意图class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(0) cur dummy carry 0 # 进位只能是 0 或 1 while l1 or l2 or carry: # 1. 取值链表为空时该位视为 0 v1 l1.val if l1 else 0 v2 l2.val if l2 else 0 # 2. 求和两个数字相加再加上上一位的进位 total v1 v2 carry # 3. 计算当前位和进位 carry total // 10 cur.next ListNode(total % 10) # 4. 指针全部向后移动 cur cur.next if l1: l1 l1.next if l2: l2 l2.next return dummy.next这段代码有几个值得仔细品味的点。第一是循环条件while l1 or l2 or carry这个条件把三种情况全部包含了两个链表都没走完、只有一个链表没走完、以及两个链表都走完了但进位还没处理完。初学者最容易漏的就是第三个情况比如5 5 10两个链表都只有一个节点相加后得到0但进位1需要额外创建一个节点挂上去如果循环条件里不写or carry这个进位就丢了。第二是取值时的v1 l1.val if l1 else 0写法。两个链表长度不一样是常态短的走完了之后它的每一位都应当视为0这样才能继续和长链表剩余部分做加法。这种长度不足就补零的处理方式比先判断谁长谁短、然后把短的数补到和长的对齐要优雅得多因为后者需要额外做链表长度的统计和节点的复制代码复杂度直接翻倍。第三是进位carry的取值范围。每一位上三个数字相加两个数位加一个进位最大也不会超过 9 9 1 19所以进位只可能是 0 或者 1。不需要考虑进位大于1的情况更不需要用数组来存储进位。这个结论看起来简单但推导一遍能帮你确认算法逻辑的完备性。3.2 循环结束后的处理最高位进位很多人写这道题循环内部的逻辑写得飞快结果在循环结束后的收尾上翻车。前面提到过while条件里包含了or carry这意味着循环本身已经处理了最后一位产生进位的情况——当两个链表都遍历完毕carry 为1时循环体会再执行一次此时两个取值都是0total 等于0加0加1等于1创建值为1的新节点然后进位变成0循环条件才彻底不满足。为了验证这个逻辑我们可以手动走一遍999 1的例子。链表分别是 9 - 9 - 9 和 1计算过程如下循环次数l1当前值l2当前值carry(进前)total当前位结果carry(进后)19101001290(链表已空)11001390(链表已空)1100140(链表已空)0(链表已空)1110最终得到的链表是 0 - 0 - 0 - 1也就是数字 1000加法结果完全正确。这个例子也是我认为每个刷这道题的人都该手动推演一遍的用例因为它把所有容易出错的点一网打尽长度不等、连续进位、最高位最终溢出产生新节点。手动走完这一遍你对这个 while 循环的信任度会提升很多面试时也能更从容地讲出循环结束自动处理了最终进位这个结论。3.3 代码实现与复杂度从复杂度角度看这个解法的时间复杂度是 O(max(m, n))其中 m 和 n 分别是两个链表的长度。因为循环的每一次迭代处理一位数字迭代次数等于较长的链表长度加上可能的最后进位多出来的一次。空间复杂度是 O(max(m, n))因为结果链表的长度大致等于较长链表长度加一。这个复杂度表现是这道题的最优解。你不可能比 O(max(m, n)) 更快了因为至少要遍历完两个输入链表才能完成计算。空间上你也不可能更省了因为必须要新建一个链表来装结果。所以如果你在面试中写出了这个解法可以明确告诉面试官这个方案的时间和空间都已经是最优的这会让你的技术沟通显得非常专业。我提供上面的是 Python 写法同样思路换成 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 v1 (l1 ! null) ? l1.val : 0; int v2 (l2 ! null) ? l2.val : 0; int total v1 v2 carry; carry total / 10; cur.next new ListNode(total % 10); cur cur.next; if (l1 ! null) l1 l1.next; if (l2 ! null) l2 l2.next; } return dummy.next; } }两种语言写法结构完全同构。我自己做这道题的经验是先用 Python 把逻辑想通再照着写一遍 Java可以快速暴露语言层面的细节差异比如 Java 的空判断更啰嗦但类型明确性更好。如果你正在准备面试建议至少用一种语言把代码背到能默写的程度。4. 边界条件攻防与测试用例设计4.1 三组必测的用例刷算法题最怕的不是不会做而是做完了不知道对不对。两数相加的测试用例设计我建议重点覆盖三种类型一种是一个数字为0的一种是两个链表长度差异悬殊的一种是连续进位的。第一组用例是0 0。两个链表各自只有一个节点值都是0。预期的输出应该是一个值为0的节点。看起来简单但如果你代码里对虚拟头节点的使用出了问题或者循环条件判断失误很容易返回一个空链表或者报空指针。这道用例是兜底用的先跑通它你至少能确认整个框架是完备的。第二组用例是1 - 3 - 5 - 79 - 2也就是 7531 29 7560。这个用例重点检验短链表走完后长链表剩余部分能不能正确补算。我在初学阶段就曾经犯过这样的错while 条件只写了while (l1 ! null l2 ! null)导致短链表访问到头之后循环直接退出长链表剩下的节点全被丢弃。用这个用例一跑错误立刻显现。正确的 while 条件是while (l1 ! null || l2 ! null)并在每次循环里对已经为空的链表取 0 作为当前位。第三组用例是9 - 9 - 91也就是 999 1。这个用例专门测试连续进位和最高位溢出。前面我手动推演过一次最终结果应该是 0 - 0 - 0 - 1注意结果链表比两个输入里最长的还多了一个节点。这一个多出来的节点恰恰是新手最容易丢的因为如果你把循环条件定成while (l1 ! null || l2 ! null)而不是带上|| carry ! 0循环在 l2 走完后就停了进位1会被遗落在循环外面代码就错了。除了这三组还可以顺手测一下5 5单次进位、1 - 82中间位不进位但高位相加产生进位。这些用例都不难构造关键是养成写完代码先设计测试用例再提交的习惯这在力扣刷题和真实工程里都是通用的基本功。4.2 常见错误清单把我在这个题目上以及看别人提交踩过的坑汇总一份清单供大家对照自查while 条件少写了or carry这是最高频的错误导致最终进位丢失结果比正确值少一个最高位。while 条件用了and而不是or一旦某个链表遍历完整个循环退出丢失长链表的剩余节点。这是对循环应该持续到什么时候理解不到位。取当前位时报空指针在链表的节点可能为空时直接使用l1.val而不是先判断if l1: v1 l1.val else: v1 0。创建结果节点时把total % 10和total // 10搞反取余得到的是当前位整除得到的是进位。这个搞反一次整个答案就是错的。忘了移动 cur 指针构建链表时必须cur cur.next否则每次新节点都挂在同一个节点后面最后返回的链表只有一个节点。对虚拟头节点的 next 判断不准应该返回dummy.next。如果你返回dummy结果链表最前面会多出一个值为占位符的节点导致整体值错误。在循环里重复处理进位比如有的人在循环末尾额外写了一个if (carry 0) { createNode(carry); }又在循环条件里加了or carry结果进位节点被创建两次。这份清单不是凭空列出来的每一条都对应着我实际见过或者写过的 bug。把这些错误做成一张检查表每次写完代码后逐条对照一遍比盲目反复提交试错要高效得多。5. 面试变体与进阶不只是两数相加5.1 正序存储怎么办力扣题库里有一道两数相加 II同样是两数相加但数字在链表里是正序存储的链表头对应的是最高位。这意味着你从头开始遍历时先遇到的是高位而不是低位不能直接套用逐位相加的流程因为进位是从低位向高位传播的而你访问的顺序恰好相反。处理正序存储有两条主流思路。一条是把两个链表反转转换成逆序存储然后按原题解法相加最后把结果再反转回去。另一条是用两个栈分别把两个链表的节点值压入弹出的时候就是低位先出等于手动模拟了从低位到高位的访问顺序。栈方案的代码相对简洁也能顺带展示你对栈这种后进先出结构的理解面试中很加分。这道变体题的考点在于你能不能识别出存储顺序影响计算顺序这个核心矛盾。逆序存储时计算顺序和遍历顺序一致正序存储时两者相反所以要通过反转或栈来对齐。理解了这一点无论题目怎么改存储方式你都能快速找到解法路径。5.2 大数相加的思路转移两数相加的链表版本本质上是大数相加Big Integer Addition问题的一种具体表现形式。所谓大数就是超过语言原生整数类型范围的长整数只能用字符串、数组或链表来存储。力扣上的字符串相加题目就是同一思路的兄弟题给你两个用字符串表示的非负整数返回它们的和同样不能用内置的大整数库。具体到实现上字符串相加的写法会更短一些因为字符串可以按下标访问任意位置不像链表只能从头部一个个往后遍历。但核心逻辑一模一样从低位往高位逐位相加维护进位最终处理可能残留的最高位进位。你在两数相加这道题里练熟的计算模式和转移逻辑可以直接平移到字符串相加二进制求和数组形式的加一等一大票题目上。这道题的变体训练价值就在这里算法题的套路不是靠死记硬背而是靠识别这类题共享同一套核心逻辑然后把核心逻辑用在不同的数据结构外壳上。在我看来两数相加就是理解这套逻辑最好的起点因为它把逐位相加 进位数学模型和链表指针移动这个编码动作结合得最干净。5.3 递归解法与迭代解法的取舍两数相加除了上述的迭代解法还有一个递归版本。递归的思路是把两个链表在当前位置相加抽象成一个函数函数里处理当前位的加法和进位然后递归调用自身处理下一个节点。伪代码大致是定义一个函数add(l1, l2, carry)它计算当前位的值创建对应节点将节点的 next 指向add(l1.next, l2.next, nextCarry)的递归结果最后返回当前节点。递归解法在代码上可能显得更高级但我个人的建议是面试中如果时间允许优先写迭代版本再补充说明递归思路。迭代版本没有递归深度限制的问题逻辑也更直观不容易在极端情况下爆栈。链表长度为 n 时递归深度就是 n如果 n 达到几千甚至上万某些环境下递归版本会直接栈溢出。当然理解递归版本对你深入理解这道题是有帮助的。递归解法天然体现了当前节点的处理只依赖当前值和下一个节点的处理结果这种分解思想和链表的递归定义结构吻合。面试官如果要求你用递归写你也要能写出来。但这道题的工程实现上迭代是更稳妥的默认选择。面试时先交一个稳妥的答案再用讨论的方式展示其他解法是我反复强调的面试策略。6. 刷题方法论一道链表题总结出的通用模板6.1 链表题四步走把两数相加这道题吃透之后我建议你主动从中总结一套做链表类题目的通用方法论这会比多做五道题还有价值。根据我的刷题经验链表题大体可以拆成四步。第一步是明确遍历的起点和方向。链表只有头节点可以访问所以几乎所有操作都要从头开始。如果题目要求从尾开始就要考虑反转或者用栈。这个判断决定了你接下来用什么结构来配合。第二步是搞清楚每个节点的访问条件。链表的长度通常不可预知所以 while 循环的条件一般是while (node ! null)或者更复杂的至少有一个链表没遍历完的组合条件。第三步是设计节点操作。新增节点、删除节点、修改指针指向操作顺序上有个铁律先处理新节点和原链表的连接关系再移动用于遍历的指针顺序反了会造成节点丢失。第四步是确认边界。循环结束之后通常还要检查一下尾部是否有残留的进位、是否需要断开某个指针、是否多了一个需要删除的虚拟头节点。这套四步法不是我凭空想出来的标准答案而是在反复写链表题的过程中自己总结的检查清单。每次遇到新链表题我都会先在草稿纸上把这四步的答案写出来再动手写代码。两数相加就是练习这套方法的第一步题目用熟了之后再看合并两个有序链表删除链表的倒数第N个节点反转链表 II这些题你的恐惧感会小很多因为骨架是同一个。6.2 从这道题延伸出去的高频题既然说了两数相加是链表操作的关键枢纽顺着这个思路往外延展有几道高频题和它的解法结构非常接近我建议你按顺序刷一遍。合并两个有序链表几乎是一道可以照抄两数相加框架的题两个链表的指针同时遍历比较当前节点的大小选择小的那个接到结果链表上然后移动对应指针。不同之处在于它不需要进位逻辑但需要处理一个链表走完另一个还有剩余的收尾。两两交换链表中的节点则是另一种风格的链表操作题不新建结果链表而是在原链表上通过修改指针来交换相邻节点顺序。它考验的是对虚拟头节点和指针顺序的掌握很多人在这个题上画出指针图才能写明白。K 个一组翻转链表则是把反转链表和链表分段两个操作组合起来是链表难题的代表。它的解法骨架依然是遍历、定位、操作、前移只是每一组的内部处理更复杂。把这个题放在两数相加之后去攻克是因为你已经有了一套顺手的链表操作模板学起来会顺畅得多。这些题目之间有清晰的梯度。如果两数相加你已经写得非常熟练了说明你对链表的基本遍历、节点创建、指针移动已经形成了肌肉记忆这时候再往难度高的题目上走每一步都会更稳当。我始终觉得刷题的数量不重要重要的是有没有在关键题目上把通用的模式吃透。两数相加就是把链表操作吃透的最佳起点这也是我写这篇分享的初衷。