1. 题目全解析这道“新手村BOSS”到底在考什么1.1 题目描述与数据规模力扣LeetCode第2题“两数相加”题面不长几句话能说清楚给你两个非空链表分别表示两个非负整数链表的每个节点存一位数字而且是逆序存储的——意思是链表的头节点存的是个位往后依次是十位、百位以此类推。要求你把两个数相加返回一个同样以逆序方式存储的和的链表。举个例子输入是l1 [2,4,3]、l2 [5,6,4]链表还原成数字分别是 342 和 465相加得到 807那输出链表就是[7,0,8]。注意中间那个 0 十位恰好是进位产生的很多新手第一次就挂在它身上。约束条件值得细看两个地方一是每个链表的节点数在 1 到 100 之间二是每个节点的值只能是 0 到 9。这意味着什么意味着你不能天真地把链表转成整数比如用int或long然后做一次加法再转回链表。100 位节点的链表还原出来是一个 100 位的十进制数远超任何语言内置整数类型的范围。就算你换成 Python 的大整数勉强能算面试官也会让你明白题目真正想考的是链表操作本身而不是语言特性。这道题在力扣上的定位很有意思属于典型的“入门偏进阶”题。它不像“两数之和”那样只要会哈希表就能秒掉也不像后面那些又臭又长的树形 DP 题目给你造成“我在做竞赛”的错觉。它刚好处在一个临界点考察链表遍历、节点构造、进位处理、边界条件全是最基础但面试经常用的东西。1.2 考点拆解链表思维、进位数学、边界意识我说“新手村 BOSS”是因为这道题一个考点都没浪费。第一个考点是链表思维。这个和数组思维不一样数组你可以随机访问任意下标链表只能从一个头节点开始拿next指针一路走下去。很多从 Pythonlist或 JavaArrayList转过来的同学第一次写链表题会下意识想“我怎么直接取倒数第二个节点”然后发现自己根本做不到只能老老实实遍历。这道题逼着你习惯这种单向、逐节点推进的思考方式。第二个考点是进位数学。两个一位数字相加最大是 9 9 18加上可能从低位来的进位 1最大是 19。所以每一位的结果可以拆成两部分当前位留在链表里的值sum % 10往高位进的数sum / 10整除这里用到的%和//运算并不难但难的是你要意识到进位不只有一次它可能沿着链表连续传下去比如 999 1 1000 这种情况。第三个考点是边界条件。这是整道题真正拉开差距的地方。两个链表长度不等怎么办短的走完了长的还剩几个节点这时候要让短的“虚拟节点”视为 0继续处理长的。两个数加完链表都走到头了但进位是 1 怎么办比如 5 5 10位数从 1 个变成 2 个你得多new一个值为 1 的节点挂上去。漏掉这个五个测试用例至少挂两个。我把这三个考点统称为刷题三板斧数据结构基本功、数学建模能力、边界条件意识。这三样东西恰好是后面几乎所有算法题尤其是链表题和模拟题反复考察的能力。所以把这题吃透性价比非常高。1.3 为什么力扣热题100里必有它如果你去看力扣的热题 100 榜单“两数相加”几乎是稳稳占住链表分类的头几把交椅。这不是没原因的。一方面它在技术面试里出现频率很高。我自己的感受是面试考链表题时难度阶梯大概是反转链表 → 两数相加 → 合并 K 个有序链表 → 环形链表检测。两数相加这个难度正好卡在“考基本功但没到劝退”的位置。面试官能通过它快速判断你熟不熟悉链表操作、能不能想到边界情况又不至于让你当场写一个红黑树出来。另一方面它是很多变种题的原型。比如力扣 445 题“两数相加 II”改成链表是正序存储解法瞬间复杂得先反转链表或者用栈比如力扣 67 题“二进制求和”本质是同一个竖式加法模型只是从十进制换成了二进制还有类似大数相加、字符串相加等题目换个马甲还是这套思路。也就是说你把第 2 题彻底弄明白后面能省出一大片时间。2. 核心算法思路从小学数学竖式说起2.1 逆序链表 个位在头天然支持加法很多人第一次看到“逆序存储”这四个字会愣一下为啥不按正常的从左到右顺序存其实这是出题人刻意降低难度。回想一下你小学做加法竖式的习惯先加个位如果满十就向十位进一再加十位。也就是说加法天然是从低位往高位算的。而链表从头到尾遍历正好也是“从头到尾”这个顺序。当链表把个位放在头节点时加法过程和链表的遍历方向就完全一致了你可以一边遍历一边算不需要任何预处理。如果链表是正序存储比如题 445 那样个位在链表尾部你就得先走到底才能开始加要么反转链表要么拿栈把节点压进去再弹出来。这等于平白多了一个步骤。所以第 2 题这种逆序设计本质上是出题人把最友好的一种形式摆在你面前了。2.2 进位处理的本质sum / 10 与 sum % 10整个算法的核心说穿了就是一句话维护好一个变量 carry表示来自低位的进位。每轮循环你做的事情是固定的取l1的当前节点值如果l1已经为空就取 0。取l2的当前节点值同理。计算total v1 v2 carry。当前位的值nodeValue total % 10。新的进位carry total // 10。这里我想强调一个容易理解错的细节进位不是carry 1或者carry 0这种布尔值而是一个整数。只是十进制里两个一位数相加进位最多是 1所以看起来像布尔值。但你如果把模型抽象成二进制字符串相加或者之后的 extension 做了多位进制carry 的取值就可能超过 1。按整数来处理代码的可泛化性强得多。还有个数学小细节total % 10和total // 10在处理 total 为 19 时得到的是 9 和 1这没问题处理 total 为 0 到 9 时得到的分别是它本身和 0也没问题。所以你在计算完最后一位之后必须检查 carry 是否还是 1如果是就得额外构造一个值为 1 的节点。这是整个算法中唯一一个“隐藏步骤”也是最容易丢的步骤。2.3 复杂度与空间占用分析时间复杂度这块你只需要把两个链表各遍历一遍循环次数等于max(len(l1), len(l2))加上末尾可能多一位的进位处理整体是O(n)。链表题很少能低于线性复杂度因为你至少要读一遍所有节点才能知道它们存储的数字。空间复杂度这块就比较有意思了如果你只用指针在原链表上改值额外空间是 O(1) 级别但标准的做法是 new 出一个新链表来存结果那么额外空间就是 O(n)n 是结果链表的长度最多是max(len(l1), len(l2)) 1。我建议用自己的新链表来存结果不推荐在原链表上改。原因是工程上你通常不愿意破坏输入数据尤其面试场合面试官更想看到你构造新链表的能力而不是“原地修改”的小聪明。当然如果你在刷第三遍、第四遍想挑战下自己原地改也是可以的但新手阶段老老实实 new 节点就好。3. 代码实现与实操要点3.1 标准解法从头到尾的完整流程Python3先贴一套我日常使用、自认为注释量刚好的 Python3 实现然后逐块拆解。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode: head ListNode(0) # 哨兵头节点 cur head carry 0 while l1 is not None or l2 is not None: v1 l1.val if l1 is not None else 0 v2 l2.val if l2 is not None else 0 total v1 v2 carry carry total // 10 cur.next ListNode(total % 10) cur cur.next if l1 is not None: l1 l1.next if l2 is not None: l2 l2.next if carry 0: cur.next ListNode(carry) return head.next这段代码里有个小设计值得说head ListNode(0)是一个哨兵节点dummy node。它的值没有任何实际意义只是为了让你在循环里能方便地cur.next ...不用单独处理“结果链表为空时第一个节点该怎么挂”的问题。最后返回head.next就把哨兵跳过了。这个技巧在链表题里太常见了反转链表、合并链表、删除倒数第 N 个节点都用得上几乎可以当成一个套路记下来。循环条件写的是while l1 is not None or l2 is not None不是while l1 and l2。原因是两个链表长度可能不一样短的走完后长的还要继续处理。我在下面的 3.3 小节会专门讨论这个细节。3.2 同思路的 C 与 Java 实现对比看 Python 代码的时候可能觉得“这也太简单了”。但面试时不一定会让你选语言有时直接让你写 C 或 Java两个语言在链表操作上的差异还是值得提前过一遍。C 版本我常用的写法class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* head new ListNode(0); ListNode* cur head; int carry 0; while (l1 || l2) { int v1 l1 ? l1-val : 0; int v2 l2 ? l2-val : 0; int total v1 v2 carry; carry total / 10; cur-next new ListNode(total % 10); cur cur-next; if (l1) l1 l1-next; if (l2) l2 l2-next; } if (carry) { cur-next new ListNode(carry); } return head-next; } };C 里最需要注意的是内存管理。new 出来的节点商业项目里肯定要负责释放但刷题时 LeetCode 会帮你统一处理。面试时如果你写了 C可以主动提一嘴“这里 new 出的节点在竞赛环境下由 OJ 统一回收在工程代码中我会用 RAII 或对象池来管理”这句话能让你显得很专业。Java 和 C 长得比较像主要区别是用new ListNode(...)拿对象引用以及判空写l1 ! nullclass Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode cur dummy; int carry 0; while (l1 ! null || l2 ! null) { 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; } if (carry ! 0) { cur.next new ListNode(carry); } return dummy.next; } }Java 的dummy变量名对应 Python 的head用哪个都行我个人习惯 Java 里写dummyPython 里写head没有特殊含义纯属代码洁癖。3.3 关键边界条件详解我经常跟人说刷题不看边界条件等于白刷。“两数相加”的边界条件总结起来就三个每个都能对应到输出结果是否正确。边界一两个链表长度不一样。比如l1 [9,9,9,9]l2 [1]。这时l2走完第一个节点后就是空指针了循环还没结束v2必须视为 0否则会出现空指针异常或者错误结果。这就是为什么while l1 is not None or l2 is not None而不是while l1 is not None and l2 is not None。一旦你用and短链表走完后循环就会提前退出长的链表剩余节点直接被丢弃结果错误。边界二最后一步进位。比如l1 [5]l2 [5]。循环里第一步算出 total10当前位节点值为 0carry1。然后两个链表都走完循环退出。如果此时你不检查 carry直接返回head.next结果就是个位 0没有十位的 1正确答案 10 被算成了 0。这种错误特别隐蔽因为你拿个位数相加的正常用例测完全看不出来。边界三结果为 0。比如l1 [0]l2 [0]。两个都是 0循环算一次total0当前位节点 0carry0循环退出carry 检查也没触发最后返回一个单独的值为 0 的节点。这个恰好是对的因为题目说数字不含前导零但 0 本身可以用单个节点表示。很多人在这个边界上担心“返回[0]算不算前导零”实际上不算题目允许。这三个边界用一组测试用例记在脑子里就够[9,9,9,9,9,9,9]加[9,9,9,9]预期结果是[8,9,9,9,0,0,0,1]。我每次写第二版代码都会拿这个用例快速走一遍因为它同时覆盖了长度不一和连续进位非常实用。4. 踩坑记录真实刷题时最容易犯的错4.1 认真检查 while 循环走出后的 carry这个坑我踩过不止一次而且我见过很多人在 LeetCode 讨论区哭诉同一个错误——写完循环直接return head.next完全忘了最后一个进位。我知道你可能会想“carry 不是在每次循环里都处理了吗”不对你处理的是当前位计算后带进下一次循环的 carry但最后一次循环结束后如果 carry 是 1它没有“下一次循环”可以传了只能额外生成一个节点。有一个技巧可以帮自己记住写代码的时候最后三行固定按这个顺序检查if carry 0: cur.next ListNode(carry) return head.next把这两步当成不可分割的一组每次写完回头扫一眼“if carry”在不在就不会漏了。我后来刷“字符串相加”“二进制求和”这类模拟题靠这个肌肉记忆省了很多调试时间。4.2 指针移动与节点构造的先后顺序很多新手第二遍自己写的时候会把顺序搞乱。比如先移动了l1 l1.next再用l1.val取值结果空指针异常或者先cur cur.next再cur.next ListNode(...)导致新节点挂错地方。正确的顺序永远是先取值 → 算结果 → 构造节点 → 挂节点 → 移动指针。顺序这个东西逻辑上并不复杂但一旦现场紧张很容易手误。我建议你在平时练习时固定一种写法形成条件反射。比如我个人习惯的固定节奏是v1 l1.val if l1 else 0v2 l2.val if l2 else 0total v1 v2 carrycarry total // 10cur.next ListNode(total % 10)cur cur.nextl1 l1.next if l1 else Nonel2 l2.next if l2 else None照这个顺序写每次循环做的事情一致且清晰几乎不会出错。4.3 把“两数相加”和“两数之和”搞混这里必须专门说一个相对冷门但真实存在的坑力扣里有两道名字极其相似的题。第 1 题叫“两数之和”Two Sum第 2 题叫“两数相加”Add Two Numbers。前者是“给你一个数组和一个目标值找出两个下标使其和为目标值”用哈希表做经典解法是 O(n)后者是“给你两个链表模拟加法”也就是本博文讲的题目。别笑真的有人面试的时候把这两个题搞混。我线下模拟面试见过一次候选人一开始大谈哈希表面试官提醒“这是链表题”他愣了几秒才反应过来。这种错误一旦发生给面试官的印象是“刷题靠死记硬背没有真正理解题目”。所以你在刷题或者复习的时候一定要看清题目输入到底是数组还是链表。4.4 递归写法的隐患递归写法确实存在而且代码很简洁class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode, carry: int 0) - ListNode: if l1 is None and l2 is None: return ListNode(carry) if carry else None v1 l1.val if l1 else 0 v2 l2.val if l2 else 0 total v1 v2 carry nxt self.addTwoNumbers( l1.next if l1 else None, l2.next if l2 else None, total // 10 ) return ListNode(total % 10, nxt)这个写法看起来优雅但有两个隐患。第一如果链表长度很大题目说最长 100 个节点递归深度其实还好只有 100 层但在某些极端的自定义测试或扩展场景里栈有溢出风险。第二对初学者来说递归的“从后往前构建链表”的过程不太好理解容易忽略nxt参数在递归返回后如何正确挂接。我的建议是第一遍刷用循环想秀操作再用递归。面试的时候除非面试官明确要求否则循环版本更加稳妥也更容易让你讲清楚每一步在干什么。5. 举一反三从这道题延伸出的刷题策略5.1 链表题目通用套路总结刷了二十来道链表题后我发现无论题目怎么变思路基本绕不开几个固定套路套路一哨兵节点。只要结果链表的“头节点”可能改变或者构造时需要统一挂接就 new 一个哨兵节点。用哨兵节点可以省掉大量“判断第一个节点是否为空”的特殊处理。比如合并两个有序链表插入删除节点的题目都能用到。套路二双指针。一个指针走前面探路一个指针在后面记录位置。查找倒数第 K 个节点、链表中点、环形链表入口全是双指针。两数相加里虽然没有明说双指针但l1和l2各一个指针同步移动本质上也属于双指针思维。套路三模拟过程。链表题不好直接数学推导的时候就模拟一遍操作过程我需要遍历哪些节点每次迭代要改哪些next循环结束条件是什么两数相加模拟竖式反转链表模拟“改箭头指向”都是这个思路。套路四画图。我在白板上刷题前一定先在草稿纸上把链表画出来用箭头表示指针移动。很多人觉得画图浪费时间其实画图是定位 bug 最快的方式。特别是涉及快慢指针、链表反转时不画图靠脑补十有八九要错。5.2 后续推荐题目与刷题顺序如果你刚刚开始刷力扣我建议跟着这条路径走第一站重返“基础关卡”。先刷“反转链表”力扣 206和“合并两个有序链表”力扣 21。这两题比“两数相加”更基础能帮你把链表的读、写、挂、断这些操作练熟。等这两道题闭着眼都能写出来再来刷第 2 题你会觉得顺畅得多。第二站挑战第 2 题的变体。推荐“两数相加 II”力扣 445它要求链表正序存储思路也简单先反转两条链表或者用两个栈把节点弹出后再做竖式加法。我的建议是用栈实现体会一下“逆序操作”在栈里的天然优势。还有“二进制求和”力扣 67和“字符串相加”力扣 415它们不是链表是字符串模拟加法但代码框架和进位处理完全一样正好用来验证你从第 2 题里提炼的解题模板是否通用。第三站回到链表经典题目查漏补缺。“环形链表”力扣 141考快慢指针“删除链表的倒数第 N 个节点”力扣 19考双指针哨兵“两两交换链表中的节点”力扣 24考递归与迭代的转换。这几道刷完链表这个分类在面试里的常见题型你基本都见过了。5.3 刷题不该只刷“题解”要刷“复盘”最后这点是我最想强调的一道题做完别急着看题解。先看自己能不能在 5 分钟内写出一个能跑的版本写出来了再去看讨论区的高票答案。如果自己的代码过了但看到别人用了更精巧的解法也别立刻改掉自己的而是想一想那个解法为什么优雅它省掉了哪些冗余步骤然后把它记在错题本里。等隔一周回来不参考任何资料再把那道题重写一遍。能把当时的 bug 和坑都避开才说明这道题你是真的会了。“两数相加”作为我的第一个“错题重写”样本效果很好。第一遍我漏了 final carry第二遍重写的时候手停在if carry前面瞬间想起上次的教训补上了。这种“痛过一次所以记住了”的体验比看十遍题解都管用。我在实际刷题中还有一个习惯把所有链表题的“边界条件”集中抄在一个文件里比如空链表、单节点链表、两个链表长度差 1、结果需要多进位等。刷到后面你会发现这些边界条件翻来覆去就这几种。把它们一次性整理成 checklist每个新题写完直接对照检查比每次都重新想一遍快得多。这道题整明白之后你也可以试着建一份自己的 checklist后头刷到任何一道链表题都能直接受益。 
长河君 · 2026/10/1 11:14:32 · 阅读 1.2k LeetCode两数相加：链表操作与进位处理的经典算法题解析
1. 题目全解析这道“新手村BOSS”到底在考什么1.1 题目描述与数据规模力扣LeetCode第2题“两数相加”题面不长几句话能说清楚给你两个非空链表分别表示两个非负整数链表的每个节点存一位数字而且是逆序存储的——意思是链表的头节点存的是个位往后依次是十位、百位以此类推。要求你把两个数相加返回一个同样以逆序方式存储的和的链表。举个例子输入是l1 [2,4,3]、l2 [5,6,4]链表还原成数字分别是 342 和 465相加得到 807那输出链表就是[7,0,8]。注意中间那个 0 十位恰好是进位产生的很多新手第一次就挂在它身上。约束条件值得细看两个地方一是每个链表的节点数在 1 到 100 之间二是每个节点的值只能是 0 到 9。这意味着什么意味着你不能天真地把链表转成整数比如用int或long然后做一次加法再转回链表。100 位节点的链表还原出来是一个 100 位的十进制数远超任何语言内置整数类型的范围。就算你换成 Python 的大整数勉强能算面试官也会让你明白题目真正想考的是链表操作本身而不是语言特性。这道题在力扣上的定位很有意思属于典型的“入门偏进阶”题。它不像“两数之和”那样只要会哈希表就能秒掉也不像后面那些又臭又长的树形 DP 题目给你造成“我在做竞赛”的错觉。它刚好处在一个临界点考察链表遍历、节点构造、进位处理、边界条件全是最基础但面试经常用的东西。1.2 考点拆解链表思维、进位数学、边界意识我说“新手村 BOSS”是因为这道题一个考点都没浪费。第一个考点是链表思维。这个和数组思维不一样数组你可以随机访问任意下标链表只能从一个头节点开始拿next指针一路走下去。很多从 Pythonlist或 JavaArrayList转过来的同学第一次写链表题会下意识想“我怎么直接取倒数第二个节点”然后发现自己根本做不到只能老老实实遍历。这道题逼着你习惯这种单向、逐节点推进的思考方式。第二个考点是进位数学。两个一位数字相加最大是 9 9 18加上可能从低位来的进位 1最大是 19。所以每一位的结果可以拆成两部分当前位留在链表里的值sum % 10往高位进的数sum / 10整除这里用到的%和//运算并不难但难的是你要意识到进位不只有一次它可能沿着链表连续传下去比如 999 1 1000 这种情况。第三个考点是边界条件。这是整道题真正拉开差距的地方。两个链表长度不等怎么办短的走完了长的还剩几个节点这时候要让短的“虚拟节点”视为 0继续处理长的。两个数加完链表都走到头了但进位是 1 怎么办比如 5 5 10位数从 1 个变成 2 个你得多new一个值为 1 的节点挂上去。漏掉这个五个测试用例至少挂两个。我把这三个考点统称为刷题三板斧数据结构基本功、数学建模能力、边界条件意识。这三样东西恰好是后面几乎所有算法题尤其是链表题和模拟题反复考察的能力。所以把这题吃透性价比非常高。1.3 为什么力扣热题100里必有它如果你去看力扣的热题 100 榜单“两数相加”几乎是稳稳占住链表分类的头几把交椅。这不是没原因的。一方面它在技术面试里出现频率很高。我自己的感受是面试考链表题时难度阶梯大概是反转链表 → 两数相加 → 合并 K 个有序链表 → 环形链表检测。两数相加这个难度正好卡在“考基本功但没到劝退”的位置。面试官能通过它快速判断你熟不熟悉链表操作、能不能想到边界情况又不至于让你当场写一个红黑树出来。另一方面它是很多变种题的原型。比如力扣 445 题“两数相加 II”改成链表是正序存储解法瞬间复杂得先反转链表或者用栈比如力扣 67 题“二进制求和”本质是同一个竖式加法模型只是从十进制换成了二进制还有类似大数相加、字符串相加等题目换个马甲还是这套思路。也就是说你把第 2 题彻底弄明白后面能省出一大片时间。2. 核心算法思路从小学数学竖式说起2.1 逆序链表 个位在头天然支持加法很多人第一次看到“逆序存储”这四个字会愣一下为啥不按正常的从左到右顺序存其实这是出题人刻意降低难度。回想一下你小学做加法竖式的习惯先加个位如果满十就向十位进一再加十位。也就是说加法天然是从低位往高位算的。而链表从头到尾遍历正好也是“从头到尾”这个顺序。当链表把个位放在头节点时加法过程和链表的遍历方向就完全一致了你可以一边遍历一边算不需要任何预处理。如果链表是正序存储比如题 445 那样个位在链表尾部你就得先走到底才能开始加要么反转链表要么拿栈把节点压进去再弹出来。这等于平白多了一个步骤。所以第 2 题这种逆序设计本质上是出题人把最友好的一种形式摆在你面前了。2.2 进位处理的本质sum / 10 与 sum % 10整个算法的核心说穿了就是一句话维护好一个变量 carry表示来自低位的进位。每轮循环你做的事情是固定的取l1的当前节点值如果l1已经为空就取 0。取l2的当前节点值同理。计算total v1 v2 carry。当前位的值nodeValue total % 10。新的进位carry total // 10。这里我想强调一个容易理解错的细节进位不是carry 1或者carry 0这种布尔值而是一个整数。只是十进制里两个一位数相加进位最多是 1所以看起来像布尔值。但你如果把模型抽象成二进制字符串相加或者之后的 extension 做了多位进制carry 的取值就可能超过 1。按整数来处理代码的可泛化性强得多。还有个数学小细节total % 10和total // 10在处理 total 为 19 时得到的是 9 和 1这没问题处理 total 为 0 到 9 时得到的分别是它本身和 0也没问题。所以你在计算完最后一位之后必须检查 carry 是否还是 1如果是就得额外构造一个值为 1 的节点。这是整个算法中唯一一个“隐藏步骤”也是最容易丢的步骤。2.3 复杂度与空间占用分析时间复杂度这块你只需要把两个链表各遍历一遍循环次数等于max(len(l1), len(l2))加上末尾可能多一位的进位处理整体是O(n)。链表题很少能低于线性复杂度因为你至少要读一遍所有节点才能知道它们存储的数字。空间复杂度这块就比较有意思了如果你只用指针在原链表上改值额外空间是 O(1) 级别但标准的做法是 new 出一个新链表来存结果那么额外空间就是 O(n)n 是结果链表的长度最多是max(len(l1), len(l2)) 1。我建议用自己的新链表来存结果不推荐在原链表上改。原因是工程上你通常不愿意破坏输入数据尤其面试场合面试官更想看到你构造新链表的能力而不是“原地修改”的小聪明。当然如果你在刷第三遍、第四遍想挑战下自己原地改也是可以的但新手阶段老老实实 new 节点就好。3. 代码实现与实操要点3.1 标准解法从头到尾的完整流程Python3先贴一套我日常使用、自认为注释量刚好的 Python3 实现然后逐块拆解。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode: head ListNode(0) # 哨兵头节点 cur head carry 0 while l1 is not None or l2 is not None: v1 l1.val if l1 is not None else 0 v2 l2.val if l2 is not None else 0 total v1 v2 carry carry total // 10 cur.next ListNode(total % 10) cur cur.next if l1 is not None: l1 l1.next if l2 is not None: l2 l2.next if carry 0: cur.next ListNode(carry) return head.next这段代码里有个小设计值得说head ListNode(0)是一个哨兵节点dummy node。它的值没有任何实际意义只是为了让你在循环里能方便地cur.next ...不用单独处理“结果链表为空时第一个节点该怎么挂”的问题。最后返回head.next就把哨兵跳过了。这个技巧在链表题里太常见了反转链表、合并链表、删除倒数第 N 个节点都用得上几乎可以当成一个套路记下来。循环条件写的是while l1 is not None or l2 is not None不是while l1 and l2。原因是两个链表长度可能不一样短的走完后长的还要继续处理。我在下面的 3.3 小节会专门讨论这个细节。3.2 同思路的 C 与 Java 实现对比看 Python 代码的时候可能觉得“这也太简单了”。但面试时不一定会让你选语言有时直接让你写 C 或 Java两个语言在链表操作上的差异还是值得提前过一遍。C 版本我常用的写法class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* head new ListNode(0); ListNode* cur head; int carry 0; while (l1 || l2) { int v1 l1 ? l1-val : 0; int v2 l2 ? l2-val : 0; int total v1 v2 carry; carry total / 10; cur-next new ListNode(total % 10); cur cur-next; if (l1) l1 l1-next; if (l2) l2 l2-next; } if (carry) { cur-next new ListNode(carry); } return head-next; } };C 里最需要注意的是内存管理。new 出来的节点商业项目里肯定要负责释放但刷题时 LeetCode 会帮你统一处理。面试时如果你写了 C可以主动提一嘴“这里 new 出的节点在竞赛环境下由 OJ 统一回收在工程代码中我会用 RAII 或对象池来管理”这句话能让你显得很专业。Java 和 C 长得比较像主要区别是用new ListNode(...)拿对象引用以及判空写l1 ! nullclass Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode cur dummy; int carry 0; while (l1 ! null || l2 ! null) { 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; } if (carry ! 0) { cur.next new ListNode(carry); } return dummy.next; } }Java 的dummy变量名对应 Python 的head用哪个都行我个人习惯 Java 里写dummyPython 里写head没有特殊含义纯属代码洁癖。3.3 关键边界条件详解我经常跟人说刷题不看边界条件等于白刷。“两数相加”的边界条件总结起来就三个每个都能对应到输出结果是否正确。边界一两个链表长度不一样。比如l1 [9,9,9,9]l2 [1]。这时l2走完第一个节点后就是空指针了循环还没结束v2必须视为 0否则会出现空指针异常或者错误结果。这就是为什么while l1 is not None or l2 is not None而不是while l1 is not None and l2 is not None。一旦你用and短链表走完后循环就会提前退出长的链表剩余节点直接被丢弃结果错误。边界二最后一步进位。比如l1 [5]l2 [5]。循环里第一步算出 total10当前位节点值为 0carry1。然后两个链表都走完循环退出。如果此时你不检查 carry直接返回head.next结果就是个位 0没有十位的 1正确答案 10 被算成了 0。这种错误特别隐蔽因为你拿个位数相加的正常用例测完全看不出来。边界三结果为 0。比如l1 [0]l2 [0]。两个都是 0循环算一次total0当前位节点 0carry0循环退出carry 检查也没触发最后返回一个单独的值为 0 的节点。这个恰好是对的因为题目说数字不含前导零但 0 本身可以用单个节点表示。很多人在这个边界上担心“返回[0]算不算前导零”实际上不算题目允许。这三个边界用一组测试用例记在脑子里就够[9,9,9,9,9,9,9]加[9,9,9,9]预期结果是[8,9,9,9,0,0,0,1]。我每次写第二版代码都会拿这个用例快速走一遍因为它同时覆盖了长度不一和连续进位非常实用。4. 踩坑记录真实刷题时最容易犯的错4.1 认真检查 while 循环走出后的 carry这个坑我踩过不止一次而且我见过很多人在 LeetCode 讨论区哭诉同一个错误——写完循环直接return head.next完全忘了最后一个进位。我知道你可能会想“carry 不是在每次循环里都处理了吗”不对你处理的是当前位计算后带进下一次循环的 carry但最后一次循环结束后如果 carry 是 1它没有“下一次循环”可以传了只能额外生成一个节点。有一个技巧可以帮自己记住写代码的时候最后三行固定按这个顺序检查if carry 0: cur.next ListNode(carry) return head.next把这两步当成不可分割的一组每次写完回头扫一眼“if carry”在不在就不会漏了。我后来刷“字符串相加”“二进制求和”这类模拟题靠这个肌肉记忆省了很多调试时间。4.2 指针移动与节点构造的先后顺序很多新手第二遍自己写的时候会把顺序搞乱。比如先移动了l1 l1.next再用l1.val取值结果空指针异常或者先cur cur.next再cur.next ListNode(...)导致新节点挂错地方。正确的顺序永远是先取值 → 算结果 → 构造节点 → 挂节点 → 移动指针。顺序这个东西逻辑上并不复杂但一旦现场紧张很容易手误。我建议你在平时练习时固定一种写法形成条件反射。比如我个人习惯的固定节奏是v1 l1.val if l1 else 0v2 l2.val if l2 else 0total v1 v2 carrycarry total // 10cur.next ListNode(total % 10)cur cur.nextl1 l1.next if l1 else Nonel2 l2.next if l2 else None照这个顺序写每次循环做的事情一致且清晰几乎不会出错。4.3 把“两数相加”和“两数之和”搞混这里必须专门说一个相对冷门但真实存在的坑力扣里有两道名字极其相似的题。第 1 题叫“两数之和”Two Sum第 2 题叫“两数相加”Add Two Numbers。前者是“给你一个数组和一个目标值找出两个下标使其和为目标值”用哈希表做经典解法是 O(n)后者是“给你两个链表模拟加法”也就是本博文讲的题目。别笑真的有人面试的时候把这两个题搞混。我线下模拟面试见过一次候选人一开始大谈哈希表面试官提醒“这是链表题”他愣了几秒才反应过来。这种错误一旦发生给面试官的印象是“刷题靠死记硬背没有真正理解题目”。所以你在刷题或者复习的时候一定要看清题目输入到底是数组还是链表。4.4 递归写法的隐患递归写法确实存在而且代码很简洁class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode, carry: int 0) - ListNode: if l1 is None and l2 is None: return ListNode(carry) if carry else None v1 l1.val if l1 else 0 v2 l2.val if l2 else 0 total v1 v2 carry nxt self.addTwoNumbers( l1.next if l1 else None, l2.next if l2 else None, total // 10 ) return ListNode(total % 10, nxt)这个写法看起来优雅但有两个隐患。第一如果链表长度很大题目说最长 100 个节点递归深度其实还好只有 100 层但在某些极端的自定义测试或扩展场景里栈有溢出风险。第二对初学者来说递归的“从后往前构建链表”的过程不太好理解容易忽略nxt参数在递归返回后如何正确挂接。我的建议是第一遍刷用循环想秀操作再用递归。面试的时候除非面试官明确要求否则循环版本更加稳妥也更容易让你讲清楚每一步在干什么。5. 举一反三从这道题延伸出的刷题策略5.1 链表题目通用套路总结刷了二十来道链表题后我发现无论题目怎么变思路基本绕不开几个固定套路套路一哨兵节点。只要结果链表的“头节点”可能改变或者构造时需要统一挂接就 new 一个哨兵节点。用哨兵节点可以省掉大量“判断第一个节点是否为空”的特殊处理。比如合并两个有序链表插入删除节点的题目都能用到。套路二双指针。一个指针走前面探路一个指针在后面记录位置。查找倒数第 K 个节点、链表中点、环形链表入口全是双指针。两数相加里虽然没有明说双指针但l1和l2各一个指针同步移动本质上也属于双指针思维。套路三模拟过程。链表题不好直接数学推导的时候就模拟一遍操作过程我需要遍历哪些节点每次迭代要改哪些next循环结束条件是什么两数相加模拟竖式反转链表模拟“改箭头指向”都是这个思路。套路四画图。我在白板上刷题前一定先在草稿纸上把链表画出来用箭头表示指针移动。很多人觉得画图浪费时间其实画图是定位 bug 最快的方式。特别是涉及快慢指针、链表反转时不画图靠脑补十有八九要错。5.2 后续推荐题目与刷题顺序如果你刚刚开始刷力扣我建议跟着这条路径走第一站重返“基础关卡”。先刷“反转链表”力扣 206和“合并两个有序链表”力扣 21。这两题比“两数相加”更基础能帮你把链表的读、写、挂、断这些操作练熟。等这两道题闭着眼都能写出来再来刷第 2 题你会觉得顺畅得多。第二站挑战第 2 题的变体。推荐“两数相加 II”力扣 445它要求链表正序存储思路也简单先反转两条链表或者用两个栈把节点弹出后再做竖式加法。我的建议是用栈实现体会一下“逆序操作”在栈里的天然优势。还有“二进制求和”力扣 67和“字符串相加”力扣 415它们不是链表是字符串模拟加法但代码框架和进位处理完全一样正好用来验证你从第 2 题里提炼的解题模板是否通用。第三站回到链表经典题目查漏补缺。“环形链表”力扣 141考快慢指针“删除链表的倒数第 N 个节点”力扣 19考双指针哨兵“两两交换链表中的节点”力扣 24考递归与迭代的转换。这几道刷完链表这个分类在面试里的常见题型你基本都见过了。5.3 刷题不该只刷“题解”要刷“复盘”最后这点是我最想强调的一道题做完别急着看题解。先看自己能不能在 5 分钟内写出一个能跑的版本写出来了再去看讨论区的高票答案。如果自己的代码过了但看到别人用了更精巧的解法也别立刻改掉自己的而是想一想那个解法为什么优雅它省掉了哪些冗余步骤然后把它记在错题本里。等隔一周回来不参考任何资料再把那道题重写一遍。能把当时的 bug 和坑都避开才说明这道题你是真的会了。“两数相加”作为我的第一个“错题重写”样本效果很好。第一遍我漏了 final carry第二遍重写的时候手停在if carry前面瞬间想起上次的教训补上了。这种“痛过一次所以记住了”的体验比看十遍题解都管用。我在实际刷题中还有一个习惯把所有链表题的“边界条件”集中抄在一个文件里比如空链表、单节点链表、两个链表长度差 1、结果需要多进位等。刷到后面你会发现这些边界条件翻来覆去就这几种。把它们一次性整理成 checklist每个新题写完直接对照检查比每次都重新想一遍快得多。这道题整明白之后你也可以试着建一份自己的 checklist后头刷到任何一道链表题都能直接受益。