1. 题目到底在考什么LeetCode 第 2 题“两数相加”我第一次刷的时候觉得不过如此——遍历两个链表逐位相加维护一个进位变量最后把结果串起来。但刷完才发现这道题能出现在各家公司的面试题库里是有原因的它表面考察链表遍历和指针操作实际考察的是你对“进位”这个数学模型的理解以及处理长度不一致、最高位多出一位等边界情况的能力。先说题目本身给定两个非空链表每个链表代表一个非负整数数字按逆序存储也就是链表的头节点是个位尾节点是最高位。比如数字 342 在链表里是 2 - 4 - 3。要求返回一个新的链表表示这两个数相加的结果同样按逆序存储。这个“逆序存储”的设计其实非常贴心因为它把数学上的低位对齐问题变成了链表遍历时的天然对齐——两个链表的头节点都是个位你从前往后遍历恰好就是从低位向高位逐位相加。这比正序存储的加法LeetCode 445 那种简单得多。正序表加法你得先反转或者用栈逆序表直接顺着走就行。这道题的适合人群很广准备校招的实习生、转码选手、社招复习数据结构的工程师甚至算法竞赛入门选手。作为面试题它考察的线段不多但关键点密集写一次就能暴露你对指针操作和边界条件的敏感度。接下来我从迭代法、递归法、字符串修改法三种思路展开重点讲讲我在实际写题和面试中被问过、踩过坑的地方。2. 迭代法面试官最想看到的解法2.1 为什么迭代法才是标准答案这道题 90% 的题解、教科书答案、以及面试官心中的标准解都是迭代法。核心原因一句话它只做了一次遍历时间复杂度 O(max(m, n))空间复杂度 O(max(m, n))结果链表的长度并且不需要额外的栈空间。整个过程就是把加法竖式的计算过程翻译成指针操作。我第一次笨拙的写法是先把 l1 和 l2 各自转换成整数加起来再把结果拆成链表。这种思路放在 Python 里能跑通因为 Python 的 int 可以无限大但在 C、Java 里 int 或 long long 直接溢出。只要链表的节点数超过 10 个一个 12 位的数字就能撑爆 int。即使题目侥幸没给你超长用例这种解法在面试官眼里也属于“绕开了出题意图”——人家考的是链表和进位你用语言特性作弊那这题等于白考。迭代法的直觉模型就是小学竖式加法。两个数字从个位开始逐位相加每一位的结果 (a b carry) % 10新的进位 (a b carry) / 10。这里的 carry 只有 0 或 1 两个取值因为两个一位数相加最大是 9 9 18再加 1 得 19进位最多是 1。这个“进位只能是 0 或 1”的性质让代码可以写得很简洁。2.2 手写迭代法从伪代码到正确实现先用一个很干净的伪代码思路初始化一个哑节点 dummyHead作为结果链表的头部占位 初始化指针 cur dummyHead用于串联结果节点 初始化 carry 0 当 l1 不为空 或 l2 不为空 或 carry 不为 0 val1 l1 为空 ? 0 : l1.val val2 l2 为空 ? 0 : l2.val sum val1 val2 carry carry sum / 10 cur.next 新节点(sum % 10) cur cur.next 如果 l1 不为空l1 l1.next 如果 l2 不为空l2 l2.next 返回 dummyHead.next这里有两个关键设计第一个是哑节点。没有哑节点的话你要先单独处理第一个节点才能让 cur 指向链表头部这会导致大量重复代码。哑节点让循环从第一个节点开始就统一操作最后返回 dummyHead.next 即可。这个技巧在几乎所有“构建一个新链表”的题目里都通用比如合并两个有序链表、链表分区、链表重排我都建议无脑加哑节点。第二个是循环条件。你要写while (l1 ! null || l2 ! null || carry ! 0)而不是while (l1 ! null l2 ! null)。后者会漏掉两种情况——两个链表长度不同时剩余的高位节点以及最高位相加后产生的多余进位。我见过太多人在这个条件上翻车链表是 [9,9,9] 和 [1]正确结果是 [0,0,0,1]但用的写法只能得到 [0,0,0]少了最高位的 1。下面是我最终提交的 C 代码加了注释class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { // 哑节点避免处理头节点空指针问题 ListNode* dummyHead new ListNode(0); ListNode* cur dummyHead; int carry 0; // carry ! 0 这个条件处理最后最高位溢出 while (l1 ! nullptr || l2 ! nullptr || carry ! 0) { int val1 (l1 ! nullptr) ? l1-val : 0; int val2 (l2 ! nullptr) ? l2-val : 0; int sum val1 val2 carry; carry sum / 10; cur-next new ListNode(sum % 10); cur cur-next; if (l1 ! nullptr) l1 l1-next; if (l2 ! nullptr) l2 l2-next; } // 记得释放哑节点或者直接用栈对象避免内存泄漏 ListNode* result dummyHead-next; delete dummyHead; return result; } };Python 版本更短class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode: dummy cur ListNode(0) 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.next注意 Python 里不需要管哑节点的内存释放这让代码看起来更清爽。C 里我在返回值之前 delete 掉哑节点很多人写题时会忽略这个内存问题但实际工程代码里这是基本功。2.3 迭代法的时间复杂度与空间复杂度时间复杂度很容易算两个链表长度分别为 m 和 n循环会遍历较长链表的每个节点再加上最后一次可能的进位新建节点所以是 O(max(m, n))。空间复杂度由结果链表决定最多 max(m, n) 1 个节点因此也是 O(max(m, n))。这里不考虑哑节点。这种复杂度分析能力在面试里几乎必问。即使你代码写对了面试官一句“这个解法的时间复杂度和空间复杂度是多少”如果你答不上来前面写对的代码会大打折扣。建议直接把“O(max(m,n)) 时间 O(max(m,n)) 空间”背下来并解释清楚 1 的那个节点来自最高位进位。3. 字符串修改法能跑但不是首选3.1 基本思路与适用场景标题里提到的“字符串修改法”本质上是一种利用语言特性的投机解法。思路分三步把链表里的数转成字符串。注意链表是逆序存储所以头节点到尾巴读出来的是“个十百千”的顺序直接读的话字符串是反转的。反转字符串得到正常的十进制表示用大数运算相加。把和的字符串再反转一次按位建链表返回。这个解法能不能用能。而且实现速度很快代码量也少。我在时间充裕、只求 AC 的时候会用尤其是 Python 环境。因为它内置的 int 转换没有溢出问题直接将两个数字转回整数相加再转链表一行加法搞定。但“能解开”和“值得在面试中写出来”是两件事。这个解法的核心问题在于它把题目想考的链表操作全部丢弃了把核心计算交给了大数库或语言特性。面试官让你做这题是想看你怎么处理进位和指针结果你一上来就把链表转成数字这跟用 Java 的 BigInteger 解题的心理逻辑是一样的——在 AC 层面是好手在面试层面是冒犯。不过也不能说这个思路毫无价值。有一种真实场景需要它如果两个数的位数特别大大到连内置大数都吃力虽然 Python 不会但某些脚本语言的数字类型有上限你会被迫实现“字符串模拟进位加法”这其实就是把链表的节点换成了字符串的字符逻辑完全一致。所以我认为字符串修改法可以作为理解题目本质的一个对照实验但不该作为面试首选。3.2 字符串修改法的实现与坑点如果你非要用字符串法或者需要写一篇说明这种思路的文章我给出实现细节def addTwoNumbers_str(self, l1: ListNode, l2: ListNode) - ListNode: def list_to_reversed_int(head: ListNode) - int: s while head: s str(head.val) head head.next return int(s[::-1]) # 先反转得到正序数字 n1 list_to_reversed_int(l1) n2 list_to_reversed_int(l2) total n1 n2 # 总和转成字符串再反转回逆序 digits str(total)[::-1] dummy cur ListNode(0) for ch in digits: cur.next ListNode(int(ch)) cur cur.next return dummy.next这段代码坑点不少如果链表的位数超过 18 位int()转换在 C / Java 中直接溢出Python 没事。这决定了此方法在 Python 和脚本语言中的可用性。处理数字 0 的边界如果两个链表都是 [0]str(total)是 0反转后 0 没问题。但如果原始数字有前导零比如链表 [0, 1]其实代表的是数字 10 而不是 01字符串反转后 int() 的处理天然正确所以这题没必要手动处理前导零但一旦你手写字符串加法而不是转 int前导零的判断就麻烦了。如果 total 恰好为 0反转后只有一位没问题。但 total 如果末尾有 0比如 120反转后是 021建链表时你要注意不要错建出多余的零节点。字符串修改法的最大教训是它把“加法过程”隐藏了。面试官追问“如果两个链表各有 10 万个节点怎么办这个解法在大整数情况下还能跑吗”你用 int 那就直接跪说用字符串模拟的话那回到的其实还是迭代法的进位逻辑只是载体不同而已。3.3 字符串法在面试中的正确打开方式我个人建议在面试中先写迭代法如果面试官问“你还有没有别的思路”再把字符串法拿出来作为讨论点。你可以这么说“还有一种取巧思路是把链表转成字符串再转整数相加。比如 Python 的 int 没有位数限制所以能跑。但这种做法忽略了链表本身的结构价值而且在大数场景下必须自己实现字符串加法本质上回到了迭代法。所以我认为迭代法才是这道题的正解。”这段话一来展示了你的思维广度二来表明你知道什么才是正确的工程视角。这比默默用字符串法 AC 后等着被追问要体面得多。4. 递归法分治思想的链表体现4.1 从迭代到递归反向链表与递归的天然契合迭代法足够好了但有些面试官会要求你尝试递归解法。递归法的本质是把“相加”这件事分解为当前位的和 对剩余链表的递归求和。这里有个看似反直觉的点链表按逆序存储头节点是个位。递归的天然执行顺序是向后递推、回溯时处理结果。如果你在递推过程中处理加法那么先处理的是个位、十位……恰好符合我们需要的低位优先顺序。所以递归法不需要先得到最长链表的长度也不需要反转链表直接在原链表顺序上递归即可因为原链表本身就是低位在前。用递归的思路拆解递归函数dfs(l1, l2, carry)返回的是从当前位开始相加的结果链表的头节点。当前位的结果 (l1.val l2.val carry) % 10。下一位的进位 (l1.val l2.val carry) / 10。递归调用dfs(l1.next, l2.next, newCarry)。基准情况l1 和 l2 都为空且 carry 为 0返回 null。如果 carry 不为 0返回一个新节点ListNode(carry)。4.2 递归实现与边界保护class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode: def dfs(node1, node2, carry): if not node1 and not node2 and carry 0: return None v1 node1.val if node1 else 0 v2 node2.val if node2 else 0 total v1 v2 carry result ListNode(total % 10) # 递归计算下一位 result.next dfs( node1.next if node1 else None, node2.next if node2 else None, total // 10 ) return result return dfs(l1, l2, 0)这个版本我看了很多题解有一半会漏掉carry 0这个条件。如果不加当两个链表都遍历完但最高位没有进位时递归会额外多创建一个值为 0 的节点导致结果多出前导零。比如 [5] 和 [5]正确结果是 [0, 1]缺了 carry 判断时结果变成 [0, 1, 0]显然错了。递归法的空间复杂度和迭代法不同。迭代法的空间是 O(max(m, n))这里的空间包含结果链表而递归法的空间复杂度应该是 O(max(m, n)) 的空间 递归调用栈的深度也是 O(max(m, n))所以总空间是 O(max(m, n))。不过递归调用栈也算空间开销面试时你最好说清楚“递归深度等于较长链表的长度所以栈空间也是 O(max(m, n))整体空间复杂度 O(max(m, n))。”4.3 迭代与递归选哪个很多学习者会纠结哪种更好。我的建议很简单面试首选迭代法。它的空间复杂度更优没有栈开销也不容易爆栈。链表长度如果是 10 万级递归深度 10 万很多语言的默认调用栈会溢出。递归法用来展示思维灵活度。如果面试官问“能不能不要额外的 next 指针”或者“你能否用递归重写”你从容地写出递归版会让面试官觉得你对解法理解得很透彻。极端场景下如果链表特别长且面试环境对栈深度有限制迭代法又成了唯一正确答案。所以结论是递归是备胎迭代是正室。两者你都要能写出来并且说清楚优缺点。5. 几种实现思路的横向对比这里用一个表格直观对比三种常见实现方案。对比维度迭代法递归法字符串修改法时间复杂度O(max(m, n))O(max(m, n))O(m n) 或 O(m n k)取决于字符串加法实现空间复杂度O(max(m, n))结果链表O(max(m, n))结果链表 递归栈O(m n)字符串存储开销进位处理显式 carry 变量显式 carry 参数隐藏在内置加法或字符串模拟中代码可读性高逻辑直白中等递归逻辑略绕高代码量少溢出风险无无Python 无C/Java 有面试推荐度强烈推荐建议掌握作为备选不推荐主动使用这个表格里我特别想强调“溢出风险”那一行。很多初学者以为字符串修改法最安全其实它不是最安全的而是语言相关的。C 里即使用long long存 64 位整数也只能支撑大约 19 位十进制数而链表随便来个 20 个节点就爆了。真正完全没有溢出风险的只有迭代法和递归法因为它们的每一步只处理个位数字。对比完三种思路你会发现这道题最优雅的地方恰恰是迭代法它把“数字相加”降维成“节点相加”每一步只处理一位无论是 3 位数还是 10 万位数对算法的影响只是循环次数而不是存储范围的扩展。这是这道题想教给你的核心思维不要试图把整个数一次性算完用进位一位一位地解决。6. 写代码时最容易踩的坑6.1 边界条件测试清单我整理了一份测试用例这些用例你在提交前一定要在脑子里过一遍或者直接画在草稿纸上。写代码前先列用例能省很多提交失败的冤枉路。用例输入预期输出备注用例1l1 [0], l2 [0][0]数字 0最容易出错的是结果出现多余的 0用例2l1 [9, 9], l2 [1][0, 0, 1]长度不同 最高位溢出最经典的坑用例3l1 [2, 4, 3], l2 [5, 6, 4][7, 0, 8]普通情况含十位进位用例4l1 [1], l2 [9, 9, 9, 9][0, 0, 0, 0, 1]一个链表比另一个长得多连续进位用例5l1 [9, 9], l2 [9, 9][8, 9, 1]每进一次位且有最高位溢出用例6l1 [5], l2 [5][0, 1]简单进位用例7l1 [0, 1], l2 [1][1, 1]注意链表 [0, 1] 实际代表数字 10不是 01这个清单是我调试时总结出来的尤其是用例 2 和用例 4覆盖了两种最常见的错误漏掉较长链表的剩余部分、漏掉最高位的最终进位。如果这两个用例过了这题的逻辑基本就稳了。6.2 实战调试技巧链表题报错时很难像数组那样一眼看出问题我分享几个调试小技巧。第一打印链表。写一个辅助函数printLinkedList(head)格式化输出每个节点比如2 - 4 - 3。在循环的每一步打印当前 l1、l2、carry、result 链表的当前状态能迅速定位是哪一步算错了。LeetCode 的 Playground 支持直接打印本地写的时候我更习惯手写一个调试输出。def debug_print(head): values [] while head: values.append(str(head.val)) head head.next print( - .join(values))第二模拟进位。在纸上模拟用例 2 的每一步l1 的 9 l2 的 1 10生成节点 0进位 1l1 的 9 l2 的空节点 0 进位 1 10生成节点 0进位 1l1 的空 l2 的空 进位 1 1生成节点 1。这个过程走完你代码里的循环条件对不对就一目了然了。第三用极小数自测。比如把链表转成数字再比对结果。这只是自测不是最终解法。我经常在提交前用这段快速验证def list_to_num(head): s while head: s str(head.val) s head head.next return int(s)用例跑完用list_to_num和 Python 的普通加法比对能查出一半问题。注意这只是本地自测最终提交还是得用迭代法。6.3 一个容易忽略的审题陷阱这道题有个不显眼的前提题目说“两个链表都是非空的”。这意味着你不需要处理入参为 None 的边界。但我在牛客网、HackerRank 等平台见过变种题那里的输入可能包含空链表。如果你在 LeetCode 提交没事换到别的平台挂了说不定就是这个原因。我建议写代码时养成习惯函数的入口处加一个空指针判断。if not l1 or not l2: return l1 if not l1 else l2虽然原题不需要但这是个好习惯也是面试时体现工程素养的细节。7. 从这一题延伸到整个算法体系刷完这题不是终点。两数相加是整个“大数加法”家族的入门题后面还有一串亲戚刷完之后你会有一种打通任督二脉的感觉。第一个延伸是字符串相加。LeetCode 415 题直接用两个字符串模拟加法不进位不反转从左到右逐位加。你会发现它的核心逻辑和链表版一模一样一个 carry、一个循环、一个结果拼接。区别只是载体从链表换成了字符串遍历方向从左到右赋值从cur-next换成了字符串追加。第二个延伸是二进制求和。LeetCode 67 题同理只是进制变了进位不再总是 10而是 2。sum a b carrycarry sum / 2result sum % 2。二进制进位最多也是 1因为 1 1 1 3除以 2 商 1。这一段理解了八进制、十六进制加法逻辑你也就全会了。第三个延伸是把链表反转和加法结合起来。LeetCode 445 题“两数相加 II”数字按正常顺序存储即链表头是最高位。这时候不能直接从前向后加因为进位是从低位往高位传播的。解法是先把两个链表反转然后按本题逻辑加最后再反转回来。或者用栈存节点弹出时从低位加起。这题用递归的思路更容易理解本质就是本题的镜像版本。第四个延伸是链表的其他高难度操作比如 K 个一组翻转链表、重排链表、回文链表。你会发现它们都用到了哑节点、双指针、循环不变量这些基本武器。两数相加这题其实就是你踏上链表操作精准控制的第一步。如果接下来你想系统性刷题我的个人建议是把 LeetCode 热门 100 题里的链表题按类型分组逐个吃透。链表题的套路就那么几种——哑节点、快慢指针、反转、合并、删除每一类专攻几题比每天随机刷一道效果强得多。最后分享一个我在实际操作中的体会两数相加这道题值得你不看答案手写三遍。第一遍照着记忆写第二遍逼自己在纸上走用例第三遍尝试用递归改写。三遍过后你会发现自己对链表的恐惧感明显减少因为你知道哪怕换一个载体、换一个进制、换一个顺序你手里都有那一套固定的解法套路。这种“套路在手”的感觉才是刷题最值钱的收获。