这两个月在后台收到不少读者留言问“链表题到底怎么入门”“刷了十几道还是没感觉”。我通常都会回一句先把力扣第2题“两数相加”吃透再说。为什么这么讲这道题表面上是“两个数字相加”实际上它的核心考点从来不是加法本身而是链表遍历、指针移动、进位传递和边界条件这四件事的组合拳。很多新手觉得它简单上手一写才发现空指针、漏进位、长度不等的情况能把人整到怀疑人生。我当年也是在这道题上栽过跟头的所以今天干脆从头到尾把它拆开揉碎讲一遍从竖式加法的本质讲到三种写法再到我实际调试中踩过的坑一次性说清楚。1. 先读懂题目两数相加到底在考什么1.1 原题描述与输入输出拆解题目原文很短给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序方式存储的每个节点只能存储一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。这里有两个关键信息容易被一带而过。第一“逆序存储”意味着链表的头节点对应数字的个位第二个节点对应十位以此类推。第二“非空链表”说明不需要处理输入为空的情况但结果链表在进位时可能比两个输入都长。举个例子l1 [2,4,3]表示数字 342l2 [5,6,4]表示数字 465相加等于 807输出链表应该是[7,0,8]。注意看结果的第二位是 0这个 0 不是“没有”而是十位相加后产生的进位把个位留空了很多初学者在这里第一次体会到“链表的每个节点都必须存在”这种和数组截然不同的特性。注意这里有个隐藏的信息点——为什么用逆序因为单链表只能从前往后遍历把个位放在头部加法就能从最低位开始逐位推进完全模拟人脑竖式计算的顺序。如果题目用正序存储那道题的难度会直接上一个台阶得先反转链表才能动手。1.2 这道题在算法面试中的真实定位力扣热题100里收录了它不是因为它难而是因为它太适合当“链表基本功”的度量衡。面试官让你写这道题真正想看的是三件事你能不能干净利落地处理“两个链表长度不一样”的情况你在最后一位产生进位时知不知道还要额外 new 一个节点你的 while 循环条件是l1 ! null || l2 ! null还是l1 ! null l2 ! null这个选择直接暴露你对边界条件的敏感度。我面试别人的时候经常在这道题上设置追问你把两个链表都走完了进位carry 1还悬在那然后呢很多候选人在这里卡壳或者写出一个 if 判断放在循环外面代码丑但能过。这两种我都见过而区别往往就是工作经验与刷题量之间的差距。所以这道题值得你花一下午不只是“AC 了就完事”而是把每一种写法、每一个边界点都彻底想明白。下面进入正题。2. 核心思路把“竖式加法”翻译成链表操作2.1 手动加法如何映射到代码咱们小时候算加法都是从右往左一位一位加个位加个位满十进一再把进位加到十位上。链表题把数字逆序存储之后这个“从右往左”刚好变成了“从头到尾”所以算法逻辑和手算完全一致。每一次循环做的事情就三件取出l1当前节点的值取出l2当前节点的值再加上上一次的进位carry。当前位的结果是sum % 10进位是sum / 10。把结果挂到新链表后面两个输入链表各自往后移动一步。用生活化一点的说法你手里有两串算盘珠子个位在最外面。你从个位开始每拨一次珠子就记一个结果满十就往下一轮记一个“1”两个串不一样长也没关系短的那串后面的珠子就当是 0。这就是这道题的全部逻辑。这里有一个新手最常见的认知偏差以为要先把链表转成整数算完再转回链表。这种思路在题目给的示例里能跑通但一旦数字超出int甚至long的范围就会炸掉。力扣的测试用例是允许链表长度到 100 的100 位十进制数远超任何基础数据类型所以必须一位一位算这也是这道题之所以存在的原因——它在提醒你不要试图走“取巧”的路。2.2 进位处理的三个细节进位是全题唯一的“算法”所在很多人代码写错就错在这里。我拆成三个细节来讲。第一个细节carry的取值只有 0 或 1。因为两个个位数相加最大是 9918加上进位 1 也就到 19所以除以 10 之后进位只可能是 0 或 1。这是这道题的简化条件不用写通用的任意进制处理。第二个细节sum % 10和sum / 10的顺序不能反。先取余得到当前位的数字再整除得到进位这个顺序对应着竖式里“写 8 进 1”的动作。有的写法喜欢用sum - 10判断进位因为知道进位只能是 1这也行但可读性不如%和/直观。第三个细节循环结束之后要单独检查carry。比如[5]加[5]结果是[0,1]。如果你只在 while 循环里处理节点循环结束就把carry丢了结果就会变成[0]少一个最高位。这个 bug 极其隐蔽因为大多数测试用例不会让你在最后一步遇到进位。但我可以负责任地说面试时十个人里有三个人会在这里翻车。从“为什么”的角度看其实是因为链表的长度是由结果决定的而不是由输入决定的。两个 n 位数相加结果最多是 n1 位这个多出来的最高位只能通过“循环结束后补节点”来实现。2.3 三个必须提前想清楚的边界情况做题之前先想边界是专业人士和初学者最大的区别。这道题有三个边界情况我建议你在写代码之前先写进注释里长度不等l1 [9,9]l2 [1]短链表走完后另一个还有节点。处理方式是短链表没节点时取值为 0继续循环。最高位连续进位l1 [9,9,9]l2 [1]结果是[0,0,0,1]。这要求循环必须走完长链表所有节点之后再去处理残留的carry顺序不能乱。结果为 0 的中间位l1 [2,4,3]l2 [5,6,4]十位 4610当前位是 0。很多新手看到 0 以为“节点不存在”直接在链表里跳过了这是概念错误——0 是一位数字必须作为节点存在。把这三个边界情况想清楚代码的骨架就出来了。3. 从思路到代码三种写法的逐步实现3.1 Python 版迭代法带完整注释我个人最推荐初学者从 Python 版开始啃因为语法噪音小注意力可以完全放在逻辑上。下面是我在力扣上提交过、后来也反复用来教学的一个版本# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode: # 虚拟头节点统一处理“结果链表为空”的尴尬 dummy ListNode(0) cur dummy carry 0 # 只要两个链表还有节点或者进位还没清空就继续 while l1 or l2 or carry: # 短链表走到头之后取值为0 v1 l1.val if l1 else 0 v2 l2.val if l2 else 0 # 当前位的总和 total v1 v2 carry carry total // 10 digit total % 10 # 挂新节点 cur.next ListNode(digit) cur cur.next # 指针后移注意判断空 if l1: l1 l1.next if l2: l2 l2.next return dummy.next我把循环条件写成了while l1 or l2 or carry而不是最常见的while l1 or l2。这样最后一位进位会直接在循环体内处理掉不需要循环外面再补一个 if。代码量更少逻辑也更聚焦。实测下来所有测试用例都能跑过。这里dummy虚拟头节点的作用值得多说一句。因为结果链表一开始是空的如果直接用cur None然后cur.next ListNode(digit)会报空指针。要么写成if cur is None: cur ListNode(...)这种分支要么直接用dummy统一处理。我的经验是链表题只要需要“从零开始构建新链表”一律先建 dummy。这个习惯能省掉你后面无数个 if 判断。3.2 Java 版实现与内存细节Java 版和 Python 版的逻辑完全一样差别在语法样板和对象引用上。先看代码/** * Definition for singly-linked list. * 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; } * } */ 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 sum v1 v2 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) ? l1.val : 0简洁地处理短链表问题和 Python 的if l1 else 0功能一致。cur.next new ListNode(sum % 10)之后直接cur cur.next中间不需要担心断链因为dummy已经把头部锁住了。Java 的int不会溢出因为每一位最大只是 19不存在两个大数相加导致 int 爆炸的问题。这也是链表加法比字符串加法省心的地方——每次只处理一位。我见过有人在这里尝试用ListNode cur null然后每次判断if (cur null)代码直接膨胀一倍。如果面试官看到你熟练地用 dummy head通常心里会给你加一分因为这说明你不是第一次写链表题。3.3 递归写法与栈溢出注意点迭代写完很多人会问递归怎么写。递归的思路很优雅函数处理当前位的和然后让next指针递归去处理剩下的节点。代码如下class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode, carry: int 0) - ListNode: if not l1 and not l2 and not carry: return None v1 l1.val if l1 else 0 v2 l2.val if l2 else 0 total v1 v2 carry node ListNode(total % 10) # 递归处理剩余节点新进位传给下一层 node.next self.addTwoNumbers( l1.next if l1 else None, l2.next if l2 else None, total // 10 ) return node递归版本看起来简洁但有三个使用前提链表长度不能太长。力扣测试用例的长度上限是 100用递归完全没问题默认栈深度一般是 1000。但如果有人拿 10 万位的链表问你递归就会StackOverflowError。这不是面试官会干的事但你需要知道这个限制。递归函数需要多一个参数carry。如果不加你就要用实例变量或者全局变量那样代码的可读性和安全性都会下降。递归的终止条件必须包含carry ! 0。[5] [5]这种情况两个链表都走完了但 carry 是 1必须还得再创建一个节点。这和我上面迭代写法里while条件包含carry是同一个道理。我不建议面试时首选递归因为不是所有面试官都喜欢递归的思路迭代的可读性更好、也不容易因栈深度被追问。但递归一定要看得懂、写得出来这也是区分“会刷题”和“懂递归”的一个侧面。4. 复杂度分析与算法优势4.1 时间复杂度与空间复杂度拆解先说结论时间复杂度 O(max(m, n))空间复杂度 O(max(m, n))其中 m 和 n 分别是两个链表的长度。时间复杂度的“为什么”很直接我们最多遍历到较长链表的末尾每经过一个节点就常数时间算出当前位的和所以循环次数等于两个链表长度的较大值。节点更长的那条链表决定了总耗时短链表在走完后按 0 处理不会增加额外开销。空间复杂度这里要特别解释一下。很多人以为“我全程只有一个 dummy 和 cur 指针空间应该是 O(1)”这个说法是错的。题目要求返回一个新链表新链表里有 O(max(m, n)) 个节点这些节点是必须分配的内存所以空间复杂度至少是 O(max(m, n))。当然如果题目允许“原地修改两个输入链表之一”来节省空间理论上可以做到 O(1)但力扣这道题并不要求我也没有推荐这么写——因为原地修改会破坏输入数据在真实工程里是要尽量避免的副作用。作为对比如果先转成整数再相加需要额外 O(m n) 的空间来存字符串或者大数结构复杂度反而更高。链表的优势在于天然不需要对齐长度因为你走完短的之后会自动补 0。4.2 为什么这个解法已经接近最优很多人会问能不能用位运算加速能不能并行计算每位的和我的回答是可以想但没必要。加法本身存在全链路的依赖关系因为进位是从低位往高位传递的第 i 位的结果依赖第 i-1 位的进位天然串行。你可以用“进位保存加法器”的思路并行计算每一位的初步和但最终合并进位的时候还是得串行走一遍。复杂度理论下限就是 O(n)因为每个节点至少要访问一次。力扣的约束 m、n 最长到 100O(n) 和 O(n log n) 在实测时间上几乎没有差别。与其考虑常数级优化不如把代码写得清晰、把边界条件处理干净。真正的优化空间在于“空间”如果要求不创建新链表可以复用两条输入链表中较长的一条在遍历时把结果写回长链表。这样空间降到 O(1)。力扣里有些题解这么写我看了也觉得精妙但代价是代码里多了不少指针判空分支面试时容易把自己绕晕。我的建议是先把常规写法练到闭眼能写再去追求这种有炫技成分的优化。而且我实习时和同事讨论过真实业务里“返回新数据”通常比“修改传入参数”更符合函数式思维也更安全。5. 实战中的常见问题与排查思路5.1 三个最经典的报错场景这道题虽然简单但提交时依然有几个高频报错。我把它们整理成一个速查表都是我当年或者学生时代真踩过的不是编的。报错类型触发场景典型错误代码正确做法运行错误空指针l1或l2走到末尾后还在访问.valwhile l1 or l2:循环内无条件l1.val先用if l1 else 0取值再判断是否移动指针答案错误丢失最高位进位[5] [5]之类最后一步产生进位while l1 or l2:循环结束后没处理carry条件带上or carry或循环外补 if答案错误结果多出节点循环条件写成while l1 and l2只处理了公共长度部分或[9] [9, 0]时多算一位明确条件用or短链表按 0 补位这三个场景里最容易自我排查的是第一个debug 时打印一下循环里的l1.val就能发现最难排查的是第二个因为大多数普通用例不会触发最后一位进位只有提交后才会被隐藏用例卡住。我的习惯是写完代码先自己构造三组用例[2,4,3] [5,6,4]、[9,9,9] [1]、[5] [5]全过再提交。5.2 测试用例设计清单刷题不止是写代码更是学怎么设计测试用例。这道题我建议你至少准备下面这些普通用例[2,4,3] [5,6,4] [7,0,8]验证最基础的加法和进位。长度不等[1,8] [0] [1,8]验证短链表补 0 的逻辑。连续进位[9,9,9] [1] [0,0,0,1]验证最高位多生成一个节点。末尾进位[9,9] [9,9] [8,9,1]验证循环结束后 carry 处理。含零结果[0,1] [0,9] [0,0,1]10 90 100中间两个零都要出现验证 0 节点不能省略。一个链表是单节点[0] [1,2,3] [1,2,3]验证循环条件对短链表为空的处理。我自己常把这些用例直接写成断言配合ListNode转列表的函数在本地跑一遍再提交。尤其是“含零结果”这个用例很多人写代码时潜意识里把 0 当成“可以忽略”这是链表的陷阱之一。5.3 刷题时容易忽略的实现细节最后补充几个代码层面容易含糊的细节都是我批改代码时反复看到的返回值是dummy.next而不是dummy。dummy本身是虚拟节点它的值 0 不是结果的一部分如果返回dummy结果链表会多出一个值为 0 的头节点。指针移动必须写在取值之后。如果你先l1 l1.next再执行l1.val那就是空指针。有的同学为了省行数把取值和移动写在一行里比如v1 (l1 : l1.next).val虽然 Python 支持但可读性很差面试时别这么写。虚拟头节点的值可以随便给但不要复用真实节点。有人为了省内存直接让dummy.next l1然后开始在 l1 上改值。能跑但会破坏输入链表而且最后的return dummy.next指向的还是原来的 l1 头万一 l1 是空的就全完了。carry在循环里的更新时机。一定是在算完当前位、创建节点之前更新否则当前位的结果会用到旧进位而且下一步用到的carry已经被覆盖了。这个时序问题用一个小例子[9] [9]推一遍就清楚了。6. 从“两数相加”延伸出去的方法论6.1 链表题的统一心法刷完这道题之后我建议你停下来做一次“元思考”链表题到底在考什么我的理解是四个字——引用操作。链表和数组最本质的区别是数组是连续内存你知道arr[i]在哪链表是分散节点你只知道当前节点和它的next。所以链表题的所有技巧都可以归结为“如何安全地操作引用”想从头部构建新链表就用 dummy 节点占位避免空指针分支。想遍历到最后就用while cur is not None而不是while cur.next is not None两者只差一个节点语义完全不同。想修改链表的连接关系就先把后续节点存到临时变量防止指针丢失。“两数相加”里我们已经用到了其中两条dummy 构建新链表、while 条件里的空值判断。这些技巧换到“合并两个有序链表”“反转链表”“删除链表的倒数第 N 个节点”时一样通用。所以我的建议是不要急着刷题量先把这道题的每个技巧的“为什么”吃透后面做链表题的速度会快很多。我自己就是从这道题开始把链表题的正确率从六成提到了九成以上。6.2 类似题目一览与进阶路径“两数相加”有个后续题“两数相加 II”区别是数字按正序存储需要先反转链表再相加或者用栈辅助。那个题能帮你进一步理解“顺序存储对算法的影响”建议在掌握本题后花一小时做掉。另外还有几个同门兄弟字符串相加把“链表”换成“字符串”题目变简单了因为没有指针操作。但思路完全一致——从低位到高位逐位相加、处理进位。二进制求和进位从满十变成满二同样是把加法的通用逻辑换一个进制。做过这道题之后你会意识到“两数相加”的核心不是十进制的具体数值而是“逐位计算 进位传递”这个通用框架。合并两个有序链表同样是双指针遍历两条链表但不需要进位比较容易入门。两数相乘进阶本质上是多次两数相加的叠加做完“两数相加”再去看理解会快很多。我个人的经验是把这些题目放在一起做一轮比单独刷十道不相关题有效得多。因为算法思维是“举一反三”的你只有在相似题之间找差异才能真正把题型特征刻进脑子里。最后说一点实际体会。我做这道题踩过最深的坑其实是那个“循环结束后补 carry”的分支。当年第一次提交测例跑过了但隐藏用例挂了当时完全没有“最后一位还可能进位”的意识。后来我把这道题当成一个模板每次遇到“逐位运算”类题目都会在代码末尾检查一遍有没有残留的进位或者借位。现在不管写字符串加法、数组加一还是二进制求和我都养成了这个习惯。说实话一道题的价值不在于它本身有多难而在于它帮你养成了什么样的预防性思维。这道题教会我的就是永远在循环结束之后再问自己一句还有没有剩下什么没处理