链表相加这道题我前后起码写过五种版本。第一次接触的是逆序版本个位顶在链表头上我当时觉得这不就是小学生列竖式嘛顺着遍历一次就能把所有节点加完。直到后来在一次模拟面试里碰到正序版本“链表相加二”才意识到同名题目完全可能藏着不同的难点。这篇文章就把我对这个题目的完整拆解、三种解法、以及反复试错后整理出来的避坑清单一次说清楚。正在准备算法面试的朋友还有想系统练链表基本功的开发者看完应该能少走几条弯路。1. 项目拆解同一个“链表相加”为什么正序版本更难1.1 两类题目对比逆序 vs 正序链表相加这个问题在常见算法题库里一般分成两个版本。第一版比较简单数字在链表里是逆序存放的也就是说链表的头节点是个位头节点的下一个节点是十位依次往后推。比如数字 243用逆序链表表示就是 3 - 4 - 2。这个版本好做的原因特别直接你从链表头开始遍历恰好就是从个位开始遍历两个链表同步往后走每一位做加法带上一位的进位循环结束就能得到结果链表而且结果链表也天然是逆序的。第二版就是“链表相加二”反过来数字在链表里正序存放。数字 243 在链表里长这样2 - 4 - 3头节点是最高位尾节点才是个位。这个版本的要求是给两个正序链表返回它们的和结果链表同样要正序存放。举个例子2 - 4 - 3 代表 2435 - 6 - 4 代表 564两者相加是 807你需要返回 8 - 0 - 7。听起来只是把顺序换了一下但做过的人都知道两个版本完全不是一个难度量级。逆序版本属于“照着直觉写就能过”的题正序版本则需要你主动做一次结构转换或者借助额外空间来改变访问顺序。1.2 真正的难点遍历顺序与进位方向是反的为什么正序版本会让不少人在白板上卡住核心原因是人脑做加法的时候是从低位往高位算的谁在链表的头部谁就是高位但你遍历链表的时候正好是从头往后。也就是说你拿到第一个节点的时候它是最有分量的最高位可它需要等待来自更低位的进位才能确定最终值。我们来做个小实验。还是 2 - 4 - 3 加 5 - 6 - 4。如果直接从头遍历第一对的节点值是 2 和 5一加得到 7你会自信地写下结果头节点 7。继续走4 加 6 得到 10得进位 1这位进位该加到十位还是百位按照正常小学加法个位 3 加 4 得 7十位 4 加 6 得 10进位 1 要给百位百位应该是 2 加 5 再加 1等于 8。所以你一开始写下的头节点 7 是错的正确应该是 8。等你发现需要改的时候头节点早就生成完了。这就是正序版本最反直觉的地方低位节点的计算结果会影响高位节点的最终值而你在遍历时先访问的是高位。这个方向矛盾不解决代码写出来要么需要在结果链表上回溯修改要么就是算错。还有一个隐藏问题两个链表长度不一样时低位到底在哪个位置加法要求个位对齐可个位在链表尾巴上。你不知道哪条链表更长也就不知道从哪个节点开始每一位恰好对齐。如果直接拿头节点互相对位短的链表前面缺的部分其实是高位补零而不是低位补零整个计算就乱套了。这一切都说明正序链表相加需要先做一次“顺序翻转”或者“尾部优先访问”的处理。2. 三种解法与选型思路反转、栈、递归2.1 反转链表法把未知问题变回已知问题我第一次认真做这道题时第一反应就是把两个链表反转。原因很简单我不想去处理遍历顺序和计算顺序相反的问题那就强行让它们一致。把两个正序链表反转成逆序链表后问题就退化成我熟悉的逆序相加版本算出结果链表最后再反转一次结果恢复到正序输出。反转链表的代码本身并不复杂核心是迭代过程中同时维护三个指针当前节点、前一个节点、下一个节点。每次先把下一个节点暂存起来再把当前节点的指针指向前一个节点然后三个指针依次后移。写几个字形容就是“改向前移再改向”。def reverse(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev这个函数是整道题的基石。我第一次写的时候犯过一个特别经典的错误没有暂存nxt就直接改cur.next结果链表从中间断掉后面的节点全丢了。这个错误我后面的避坑章节还会详细说。反转之后两个链表都能做到“从个位开始”相加。这里有个值得分享的小优化结果链表的构建方式直接决定你要不要做最后一次反转。如果用尾插法构建结果链表也就是新节点一直追加到末尾那么先算出的低位会在结果链表头部最后整体反转一次才能得到正序。如果用头插法构建也就是每次把新节点插到链表头部那么先算出的低位会随着后面高位节点的不断插入慢慢沉到链表尾部最后得到的链表天然就是正序的从而省掉最后一次反转。这也是为什么我强烈推荐“反转链表 头插法构建结果”的组合整体只需要反转两个输入链表输出链表不用再碰。2.2 栈辅助法用空间换取“不破坏入参”反转链表法思路清晰但它有一个副作用它会原地修改入参。如果面试官或者业务场景要求两个输入链表不能被破坏反转法就不合适了。这时候栈就派上用场了。栈的天然特性是后进先出。我把链表从头节点开始依次入栈先入栈的是高位最后入栈的是低位。出栈时正好反过来第一个弹出的是个位第二个弹出的是十位。这等于完全不用改链表指针就拿到了“从低位到高位”的访问顺序。两个链表各自建一个栈弹出时同步相加逻辑跟逆序版本几乎一模一样。栈的额外开销是 O(n) 或 O(m)取决于两个链表的长度反正整体是线性空间。带来的好处也很明显不修改入参代码不容易出错压栈和出栈的操作非常直观。在面试现场如果想快速给面试官一个“肯定正确”的方案栈法是性价比很高的选择尤其当你的心态有点紧张的时候那些指针操作越少代码越不容易写崩。我在实际编码中更喜欢这样的栈实现不重建栈链表只定义一个head None每次计算结果都头插新节点。这样结果链表也不需要一个 dummy 节点和尾指针逻辑很干净。2.3 递归对齐法补零操作的妙用还有一种思路很多人会提就是递归。递归能自然地走到链表末尾相当于“尾部优先访问”。问题是两个链表长度可能不一样递归时一个链表已经为空另一个还剩一截加法就没法对齐了。所以递归法要先计算两个链表的长度然后把较短的链表前面补若干值为 0 的节点让两个链表长度一样。补零的思想很漂亮一个数字在最高位前面补 0数值不会变。比如 56 和 4056 相加把 56 补成 0056位数就对上了。补零完成后递归从尾部开始逐层返回每一层算当前位置的两个节点值加上来自更低位也就是后驱节点的进位生成新节点同时把进位继续往上一层抛。这种写法的优点是代码看起来非常“巧”充分展示了对链表和递归的理解。缺点是递归有栈深度限制链表长度很大的时候会爆栈而且需要维护多个返回值写起来容易手滑。实际面试中我不建议把它作为主推方案但如果面试官追问“还能怎么做”把递归对齐法讲出来能加分表明你不是只会背模板。3. 完整实现从代码到复杂度逐步敲给你看3.1 反转函数与头插法配合为什么可以少一次反转前面提到头插法构建结果链表能让输出自动正序这背后其实藏着一层逻辑关系反转两个输入链表后第一次计算的节点来自两个原始链表的尾部对应的是整个数字的个位。个位在结果里应该在链表的最后位置而头插法的特性是新节点依次成为新的头节点先前插入的节点会被一步一步推远。第一次插入的节点最终会停在链表的最后正好是它应该待的位置。用 243 564 来验证两个链表反转后分别是 3 - 4 - 2 和 4 - 6 - 5。第一次计算 3 4 7得到节点 7插入空链表链表现在是 [7]。第二次计算 4 6 10结果节点 0插入头部链表变成 [0, 7]。第三次计算 2 5 1 8结果节点 8插入头部链表变成 [8, 0, 7]。这就对了。如果反过来用尾插法第一次插入节点 7 会停在链表头部结果就成 [7, 0, 8] 了需要额外 reverse 一次。所以头插法和反转操作是绝配这是很多初学解法里没点透的细节。3.2 主流程实现与进位处理详解下面给出我比较满意的一个完整实现代码直接把反转后的链表相加然后用头插法构建结果class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverse(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev def addTwoNumbers(l1, l2): r1 reverse(l1) r2 reverse(l2) carry 0 head None while r1 or r2 or carry: total carry if r1: total r1.val r1 r1.next if r2: total r2.val r2 r2.next carry total // 10 digit total % 10 node ListNode(digit) node.next head head node return head主流程里最容易忽略的是while r1 or r2 or carry这个条件。很多人写while r1 and r2等到短链表走完就退出循环长链表剩下的部分直接被扔掉结果完全错误。正确做法是只要两个链表还有节点没处理或者进位还等于 1循环就必须继续。进位变量carry的更新方式也很固定把当前位的三部分两个加数节点的值以及上一位进位加在一起总和大于等于 10 就向下一位进 1。Python 里直接用total // 10取整除当前位保留total % 10。最高位进位的情况尤其要注意比如 999 1所有位都是 9计算到最后carry还是 1循环条件保证它不会漏掉最终会多出一个值为 1 的新节点。3.3 三种方案的复杂度对比与面试表达我在准备这类题目时习惯把不同方案的复杂度放在一张表里对比这样面试时不管问哪种都能答得出来方案时间复杂度额外空间复杂度是否修改输入链表适合场景反转链表法O(n m)O(1)会修改输入数据可改变追求最优空间栈辅助法O(n m)O(n m)不会修改要求数据只读代码优先正确递归对齐法O(n m)O(max(n, m))不会修改链表较短展示递归技巧面试的时候我一般会先说思路而不是立刻埋头写码。讲思路的顺序是先承认这道题的正序性质给常规遍历造成困难再提出反转方案解决访问顺序问题然后用头插法避免结果链表的额外反转最后提一句“如果输入链表不能修改可以改用栈方案”。这套话术能在三五句话里让面试官看到你对问题本质和方案取舍都有理解。很多人面试时一上来就写代码结果写一半发现方向不对还要推翻重写反而扣分。先花一两分钟说清方案再动手整个过程会更稳。4. 边界条件与避坑指南实测中容易翻车的地方4.1 边界用例清单从两个5到999加1我在本地测试这个算法时会特意准备几组用例它们分别覆盖不同类型的边界情况。这里直接列出来供你参考测试用例输入链表代表数字期望结果验证点l1[5], l2[5]5 5[1, 0]最高位进位l1[9,9,9], l2[1]999 1[1, 0, 0, 0]连续进位结果比最长链表还长一位l1[0], l2[0]0 0[0]结果必须返回节点不能返回空l1[1,2,3], l2[4,5,6]123 456[5, 7, 9]无进位的普通情况l1[1], l2[9,9]1 99[1, 0, 0]长度差较大且带进位这些用例跑通之后代码的正确性基本就有底了。其中最容易漏的是[5] [5]这种它验证的是两个链表都只有一个节点且相加会超过 10 的情况。如果不加carry进循环条件结果只会是 [0]丢掉了最高位的 1。4.2 写码时最容易犯的三个错误翻车点一反转链表时丢失 next 指针。初始状态cur指向头节点如果没先nxt cur.next当执行cur.next prev时cur的原始后继就彻底找不回来了。链表从中间被剪断后半段直接丢失。解决办法就是养成条件反射每次反转前先保存nxt。翻车点二循环条件写成while r1 and r2。一旦较短链表遍历完循环立刻终止较长链表剩余部分没有和进位叠加结果自然错。这种错误尤其隐蔽因为如果两组数据长度相同代码表现一切正常一旦出现长度不一致就出问题。我自己就有一次在模拟面试时犯了这个错面试官随手出了个[1] [9, 9]马上现出原形。翻车点三忘记处理最高位最后的进位。carry在最后一次循环可能仍然是 1比如[5] [5]或者[9, 9] [1]。如果循环条件里没有or carry或者循环结束后没判断if carry结果链表就会少一个最高位节点。这个 bug 也是最常见的答案输出比预期少一位的原因。4.3 这类链表题的通用调试技巧做链表题目肉眼盯着代码找 bug 的效率很低。我自己的习惯是写一个辅助函数把链表转成 Python 列表打印出来每次操作完直接print一下中间状态。def linked_list_to_list(head): res [] cur head while cur: res.append(cur.val) cur cur.next return res反转前先打印一次反转后再打印一次加法过程中也可以在每个循环末尾打印当前结果链表。看到实时数据流错误往往一眼就能定位。尤其是上面提到的那三个经典翻车点每一步的打印输出都指向明确的错误位置。还有一个经验在真正进入主流程代码前先单独测试reverse函数确保它对空链表、单节点链表、多节点链表都能正确工作。reverse是这个题目的核心基础它没问题后面的加法逻辑才值得继续调试。这种自下而上的验证顺序比写完整个算法再回头找问题要高效得多。我个人在实际操作中的体会是“链表相加二”考的不只是你会不会竖式加法而是你能不能把“访问顺序与计算顺序相反”这个矛盾通过反转、栈、递归这些手段转化成已知问题。反转方案训练的是基础指针操作栈方案训练的是空间换时间的取舍意识递归方案训练的是递归边界设计。三种都写一遍你对链表方向感的理解会比只背一个解法扎实得多。最后再分享一个小技巧如果你担心自己写的reverse有问题就把反转后的链表用打印函数输出然后和高低位手算的结果对一遍。这个习惯帮我避开了无数次藏在细节里的崩溃。这道题之后的扩展也很有意思比如从加法推广到链表大数乘法或者把栈方案改成双端队列配合字符串处理都是同样的思路。先把这版吃透后面的路就好走多了。