刷力扣hot100的时候很多朋友一看到链表题就头疼特别是“两数相加”这种既要处理链表遍历、又要处理进位的题。这道题在力扣上属于经典中的经典hot100里序号126有些版本编号不同但无论编号怎么变它的核心思路完全一致用链表模拟竖式加法。今天这篇就把这道题从读题到优化讲透顺便把链表题里经常踩的坑一并说清楚适合刚开始刷链表、或者链表基础不牢的朋友。先说清楚这道题到底在做什么给两个非空链表每个节点存一个0到9的数字数字在链表中是逆序存储的也就是说链表头节点是个位接着是十位、百位以此类推。要求把两个数相加返回一个新的链表同样逆序存储。比如2 - 4 - 3表示3425 - 6 - 4表示465两者相加得到807对应链表7 - 0 - 8。这就是一个典型的“竖式计算”过程只是把纸面上的列竖式翻译成了代码。1. 题目本质与解题方向拆解1.1 读懂题目藏在细节里的信息这道题表面简单但读题的时候有几个细节必须抓住漏掉任何一个都会在后面的实现里给你脸色看。第一链表的顺序是反的。正常写数字我们习惯高位在前比如807写成8 - 0 - 7但题目偏偏给出了逆序存储。很多新手一开始不习惯容易在拼接结果链表时把顺序搞错。实际上逆序存储反而是个好消息——因为加法本来就要从个位开始算链表头已经帮你排好了个位你不需要额外翻转直接从头节点开始遍历就是标准竖式的从低位到高位。第二两个链表的长度可能不一样。比如9 - 9 - 9 - 9 - 9和1 - 2 - 3相加短的链表先走完长的还剩下一截。这时候要怎么处理竖式加法里短的数高位就当0来算代码里就需要判断一个链表为空时把该节点的值当作0来参与运算。第三进位可能让最终结果多出一位。比如9 - 9和1相加个位9加1等于10写0进1十位9加进位1等于10写0进位1最后还要再补一个节点存最后的1结果是0 - 0 - 1表示100。这个“循环结束后如果进位不为0还得再new一个节点”的细节我见过无数人漏掉。第四题目给的数字不会以0开头除非这个数本身就是0。这意味着头节点为0的情况只有一个两个数相加为0或者单个数字0加单个数字0。这个约定其实是简化了你可能要考虑的“前导零”问题不需要额外处理。把题目里这些隐藏信息摸透再动手写代码思路会顺很多。很多人在链表题上卡壳其实不是代码能力不行而是根本没把题目条件翻译成实现约束。1.2 两条路线转数字 vs 直接模拟竖式加法看到这道题很多人的第一反应是把两个链表转成数字相加再把结果转回链表。思路本身没有错但需要想清楚边界条件。如果链表短数字小这条路完全可行。Python里甚至可以直接用字符串拼接再转int几行代码就写完。但链表长度一旦超过语言整数类型的最大范围比如Java的long最大约9.2乘以10的18次方也就是19位十进制数而链表节点数可以达到100个甚至更多直接转数字一定会溢出。就算用BigInteger之类的工具类本质上也是绕开了题目想要考察的“链表操作”和“进位处理”。面试或者刷题的目的在于练习数据结构走捷径能AC但收获有限。真正值得掌握的方案是直接在链表上模拟竖式加法同时遍历两个链表每次取出两个节点的值加上上一位的进位得到当前位的和。如果和大于等于10就产生进位1因为是两个个位数相加再加上进位1最大是9 9 1 19进位最多是1。当前位置存的数字是和除以10的余数也就是sum % 10进位是sum / 10。循环直到两个链表都为空且进位为0。这两条路线一对比高下立判。转数字适合当玩笑解法或者用来验证答案真正要掌握的是模拟竖式的写法。这也符合力扣hot100题的定位——它考的不是你会不会用现成工具而是你能不能把底层逻辑用代码表达出来。2. 核心细节链表操作与进位处理的三个关键点2.1 虚拟头节点让边界处理变成统一逻辑链表题里有一个几乎万能的小技巧就是引入虚拟头节点dummy。它的作用是当你需要构建一条新链表时不用针对“当前是不是第一个节点”写两套逻辑。拿本题举例结果链表的第一个节点存的是两个链表第一个节点的和取余。如果不用dummy你得先单独处理第一个节点然后移动指针如果用了dummy你只需要让一个游标指针cur先指向dummy每次算出新节点就执行cur.next newNode; cur cur.next循环结束后直接返回dummy.next即可。这个技巧我建议所有刷链表题的人都养成习惯。它不仅让代码更简洁更重要的是减少了一种边界情况的思考负担你不需要随时反问自己“当前节点是不是头节点”b因为dummy帮你占住了头节点的位置真正的头节点永远可以通过dummy.next拿到。只要是“需要从头构建一条新链表”的题目比如合并两个有序链表、链表排序这个套路几乎通用。2.2 进位的计算与传递核心中的核心进位的处理是这道题的灵魂也是最容易出bug的地方。很多人的第一版代码会写出类似这样的大白话逻辑int sum val1 val2 carry; if (sum 10) { carry 1; sum sum - 10; } else { carry 0; }这样写没问题但不够简洁而且容易漏掉sum恰好等于10的情况。更稳妥的写法是直接利用整数除法int sum val1 val2 carry; carry sum / 10; sum sum % 10;因为两个个位数加进位最大是19所以carry只会是0或1。用sum / 10得到的值天然就是进位不需要再手动if判断。至于当前位的结果用sum % 10取个位数字即可。需要注意的一个坑是如果两个链表都遍历完了但carry仍然是1说明最高位存在进位。这时候一定要再创建一个值为1的新节点接到结果链表末尾。这一步很多人写循环的时候压根没想到只有跑测试用例才发现9 1 0少了个十位的1。进位传递还有一个容易忽略的点carry必须定义在循环外面不能定义在循环体内部。因为每次循环结束时计算出来的进位要带到下一次循环如果定义在循环里面每次进去就重置成0了相当于把进位弄丢了。这个错误也相当常见。2.3 循环条件与边界处理的正确姿势循环条件的写法可以有好几种但背后逻辑要一致。最容易理解的版本是只要两个链表有任何一个还没走完或者还有进位就继续循环。while (l1 ! null || l2 ! null || carry ! 0) { int val1 (l1 null) ? 0 : l1.val; int val2 (l2 null) ? 0 : l2.val; int sum val1 val2 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; }把carry ! 0也放进循环条件等于把“循环结束后补最后一位”的处理逻辑前移了。循环结束的唯一条件是两个链表都空且进位为0也就是说结果已经完整生成不需要在循环外面再补节点。这种写法我个人最推荐因为逻辑完整不容易遗漏。从代码里还能看出一个细节在移动指针时要判断当前节点是否为空再移动不能直接l1 l1.next否则当l1为空时会抛出空指针异常。这个判断看似不起眼却是链表遍历里最常见的崩溃原因。另外两个输入的链表节点也可以复用直接把结果写在l1上节省空间。但这会修改原始输入如果面试时面试官允许可以做如果不允许还是老老实实创建新节点。我平时刷题默认不修改输入数据养成习惯后遇到“要求不修改原数组/链表”的题目不会慌。3. 代码实现与逐步解析附Python和Java可运行版本3.1 Python版本清晰优先的写法Python写链表题有它的独到优势代码短、可读性好。定义一个节点类class ListNode: def __init__(self, val0, nextNone): self.val val self.next next然后是核心函数def add_two_numbers(l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(0) cur dummy carry 0 while l1 or l2 or carry: val1 l1.val if l1 else 0 val2 l2.val if l2 else 0 total val1 val2 carry carry total // 10 cur.next ListNode(total % 10) cur cur.next if l1: l1 l1.next if l2: l2 l2.next return dummy.next这里有几个值得解释的点。while l1 or l2 or carry这个条件把三种情况都圈进去了。val1 l1.val if l1 else 0如果l1为空就取0相当于自动补齐了短链表的缺失位。total // 10算进位total % 10算当前位这两个操作代替了if判断。整个代码不到10行但完整处理了所有边界条件。我建议初学者把这段代码在纸上手动走一遍用例就是2 - 4 - 3加5 - 6 - 4。逐步记录cur的移动、carry的变化、结果链表的生成过程一定会有种“哦原来如此”的感觉。3.2 Java版本工程化写法与注意事项Java版的思路和Python完全一致区别在于语言语法和类型声明。如果面试题目要求用Java写可以这样写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 val1 (l1 null) ? 0 : l1.val; int val2 (l2 null) ? 0 : l2.val; int sum val1 val2 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; } } return dummy.next; }Java版本里需要注意的细节三元运算符(l1 null) ? 0 : l1.val帮我们处理了空指针问题carry sum / 10利用整数除法得到进位最后返回dummy.next而不是dummy因为dummy是我们自己创建的占位节点真正的链表头是它的下一个节点。这道题如果用C写思路完全一样只是用ListNode*指针。我的经验是先把Python版吃透再用Java版或者C版多写几遍直到能闭着眼默写出来。算法题的核心是思路但落实到不同语言的语法细节也要做到心里有数。3.3 复杂度分析与空间优化思路时间复杂度方面两个链表各遍历一遍循环次数最多是max(len1, len2) 1加一是因为最后可能多出一位进位所以时间复杂度是O(n)n是较长链表的长度。空间复杂度方面新创建了一个链表节点数是max(len1, len2) 1空间复杂度也是O(n)。如果不考虑结果链表占用的空间只算额外变量dummy、cur、carry那额外空间就是O(1)。空间优化有一个思路不创建新链表把结果直接写在l1上。每次取l1节点作为结果节点如果l1先走完就切换到l2。这样省去了创建节点的操作但代码会变得稍微复杂而且要处理l1走到头的情况。我个人在刷题阶段不太推荐这种做法因为正确性优先空间复杂度在这个题目里不是瓶颈掌握标准写法更划算。如果后续在嵌入式等内存受限的环境遇到类似问题再考虑原地修改的方案。4. 常见问题与排查技巧实录4.1 最容易踩的坑漏掉最后一位进位这个我反复提到了但还是要单独拿出来说。测试用例[9,9]和[1]正确结果是[0,0,1]。很多人的代码跑出来是[0,0]原因就是循环结束后没有检查carry是否为1。如果你用的是while (l1 ! null || l2 ! null)循环结束后必须加上if (carry ! 0) { cur.next new ListNode(carry); }如果你用的是while (l1 ! null || l2 ! null || carry ! 0)那就天然处理了这个情况这也是我更推荐后者的原因。4.2 警惕空指针链表越界的两个细节第一个细节是在循环内部取节点值之前要先判断节点是否为null。比如不能用l1.val直接取值万一l1比l2短先一步变成null再用l1.val就会空指针。必须写成int val1 (l1 null) ? 0 : l1.val。第二个细节是在移动指针时不能无脑l1 l1.next。当l1已经是null时.next就会抛异常。要写成if (l1 ! null) l1 l1.next。这两个细节出现的频率非常高尤其是刚开始写链表题的朋友经常在一道题上同时踩这两个坑。排查的时候可以打印日志每次循环打印val1、val2、sum、carry很快就能定位到是哪一步出了问题。4.3 常见问题速查表问题现象可能原因排查方法运行报空指针异常取节点值时没判断null或移动指针时没判断null检查l1/l2为null的情况是否都有if保护结果少了一位循环结束漏掉carry不为0的处理确认循环条件包含carry ! 0或循环后补判断结果多出前导0比如[0,5]而不是[5]非0数开头的链表节点值为0被一起加进去了检查是否多创建了进位0节点确认最后一位进位才需要补节点大数测试用例出错使用了转数字再相加的方案数字溢出改用逐位模拟竖式加法的标准解法超时死循环比如指针移动条件写错检查循环内l1/l2是否在正确前进循环条件能否正常退出结果链表顺序反了没有理解逆序存储把个位当高位处理回顾题目头节点是个位直接从头遍历就是正确顺序这个表格里的情况基本都是真实刷题时会遇到的尤其第二条和第四条几乎是每个刷这道题的人都会犯的错。我自己第一次写这题时漏了最后一位进位调试了半天才意识到问题在哪。4.4 我调试这道题时用的小技巧分享几个调试链表题的实用小技巧。一是写一个打印链表的辅助函数。链表在LeetCode的测试用例里显示为数组格式[2,4,3]但实际运行中你想看它变成了什么光靠debugger有时候不直观。写一个简单的遍历打印函数在关键步骤后打印当前结果链表比断点调试快得多。二是在纸上画图。链表的指针操作闭上眼睛在脑子里想很容易乱但在纸上画出每个节点的指向模拟pointer的移动基本不会错。我刷链表题的习惯是先画图再写代码。三是用极端case自测。写完之后至少跑这几个用例两个链表长度相同有进位[9,9][1]两个链表长度不同[1,8][0]结果为0[0][0]多个连续的进位[9,9,9][1]用这几个用例验证过后代码的健壮性基本就有保证了。5. 变体题型与后续刷题建议5.1 同类型题目的横向对比两数相加这题吃透了可以顺带过一遍同类型的题目一举打通“加法类链表题”。最直接的变体是力扣445题“两数相加 II”。这题的数字是正序存储的也就是高位在链表头比如7 - 2 - 4 - 3表示7243加5 - 6 - 4得到7 - 8 - 0 - 7。由于加法必须从低位开始算而链表的低位在末尾你不能直接从头遍历要么把两个链表翻转后按原题逻辑处理再把结果翻转要么借助栈来实现从末位开始的加法。这里涉及的“翻转链表”操作也是hot100里的基础操作建议提前掌握。另一个相关的思路是字符串加法。把两个数字字符串相加比如123 456 579和本题的逐位加法思路几乎一模一样只是把链表节点换成字符串字符返回值也从链表变成字符串。这类题目练习的是同一个核心能力从低位到高位逐位计算处理进位处理好长度不一致的问题。如果把思路再扩展一下二进制求和、大整数乘法等题目也都是同一个套路只是进制不同或者多了个累加过程。所以我说这道题是“链表加法类题目的母题”一点不过分。5.2 从这道题延伸到hot100的正确刷题姿势力扣hot100是很多人的刷题清单100道题说多不多说少不少关键是怎么刷。第一不要按题目顺序无脑刷。hot100的题目在力扣上有单词页但顺序不代表难度梯度。我的习惯是按专题刷先刷数组和链表的基础题比如两数之和、合并两个有序数组、反转链表再刷双指针、滑动窗口然后二叉树再动态规划。这样每个专题内的题目思路有延续性刷起来不容易断层。第二一道题至少刷三遍。第一遍看题解看懂思路照着敲一遍第二遍隔一天关掉题解自己写第三遍过一周再做一遍目标是能一次通过。三遍之后这题基本就是你的了。这种方法虽然慢但比做十道新题都有用。第三要及时总结。我自己的习惯是每道题记录三行笔记核心思路是什么踩了什么坑有没有同类题可以对比。有些题开始觉得难过了一个月回头看发现超简单这种“变简单”的感觉就是进步的直接证明。第四不要死磕一道题。一道题想30分钟没有思路就看题解看懂后照着写一遍然后关掉自己再写一遍。刷题的意义是熟悉套路积累经验不是证明自己天赋异禀。我见过太多人死磕一道题几小时最后既浪费时间又打击信心完全不划算。这两数相加的题本身难度不大但能在它身上学到的东西很多链表遍历、dummy节点、进位处理、边界判断全都在里面了。把这些细节吃透后面碰到任何链表题你都会感谢今天认真分析了这20多行代码的自己。最后再说一个我自己的习惯每道题AC之后我会在提交记录里看一眼别人的高赞解法对比一下自己的代码差距在哪。两数相加这题有人用递归写有人用迭代写有人用了更简洁的条件判断。多看看别人的思路自己的代码才会越来越精致。