LeetCode两数相加链表题详解：虚拟头节点与进位处理的面试避坑指南

从LeetCode第2题聊起，这是一道被无数人称为“入门友好，但坑不少”的链表模拟题。标题里的两数相加，指的是给你两个非空链表，每个节点存一位数字，数字按逆序存储，要求你把两个数加到一起，再以同样的链表形式返回结果。比如(2 -> 4 -> 3)加上(5 -> 6 -> 4)，得到(7 -> 0 -> 8)，也就是 342 + 465 = 807。很多刷题网站把它放在“链表”分类的第一题，但真正动手写起来，链表的指针操作、进位处理、边界判断，每一项都值得掰开揉碎讲清楚。

这篇内容我打算按自己的学习路径来写：先讲清楚题目到底在考什么，再上竖式加法的思路，然后给能直接跑的代码，最后讲面试官最爱追问的变体和坑。不管你是在准备算法工程师面试、刷蓝桥杯，还是单纯想补数据结构与算法的基础，这篇都能当一份可复用的笔记。我写的时候会把每一步拆到最细，连测试用例怎么构造都会说，因为那些“隐藏的分数”往往就藏在边界条件里。

1. 题目拆解：先把两个容易混的“求和题”分清楚

1.1 “两数之和”和“两数相加”根本不是一道题

很多刚刷题的人会把LeetCode的第1题和第2题混在一起，因为中文翻译都带“两数”两个字。这里必须先把目录理清楚：第1题 Two Sum（两数之和）是在数组里找两个数，使它们的和等于目标值，返回下标；第2题 Add Two Numbers（两数相加）是给你两个链表，模拟竖式加法，返回新链表。前者考的是哈希表或暴力枚举，后者考的是链表遍历与进位处理。面试时如果连题目都没分辨清楚，后面的一切都白搭。

这个区分也直接决定了我们应该用什么复习策略。如果你准备的是算法工程师面试，这两题都需要会，但“两数相加”更侧重于模拟过程，它不需要你像 Two Sum 那样想“怎么快速查找”，而是要求你老老实实把“逐位相加、逢十进一”这个过程用链表指针实现出来。说白了，它考的是基本功扎不扎实，以及边界情况想得全不全。

1.2 链表的数据结构基础：节点和指针

在写代码之前，先复习一下链表的最小单元。链表由一个个节点构成，每个节点存两个东西：一个val存当前位的值，一个next指向下一个节点。最后一个节点的next指向null。这种结构在物理内存里不连续，靠指针串起整条链，所以遍历的时候只能从头节点一个一个往下走，没法像数组那样直接按下标取值。

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; } }

这段定义是LeetCode默认提供的节点结构，蓝桥杯、力扣风格的在线评测也都大同小异。实际面试手写时，也可以直接用内部类定义一个简单的Node，但最好先问清楚对方平台有没有预设结构，别自己另起炉灶。

回到题目，题目说数字是逆序存储，意思是链表的头节点是个位，下一个节点是十位，再下一个是百位。为什么要这样设计？因为加法本来就该从低位开始算，逆序存储让我们从head一路往后走的时候，正好就是从个位往高位走，省掉了反转链表的操作。这是题目的一个“送分设计”，但面试官反手就会问：“如果数字是正序存储的，比如3 -> 4 -> 2表示 342，你怎么办？”这个问题我留在后面第4节专门展开。

1.3 题目到底在问什么：模拟竖式加法的全过程

我们先看看题目给出的示例。l1 = [2,4,3]，l2 = [5,6,4]，链表表示的是 342 和 465。从个位开始加：

• 个位：2 + 5 = 7，没有进位，结果个位是 7。
• 十位：4 + 6 = 10，写下 0，向百位进 1。
• 百位：3 + 4 + 1（进位）= 8，结果百位是 8。

所以结果是链表7 -> 0 -> 8，对应数字 807。这个例子其实已经把最关键的两个要素都暴露出来了：一位相加可能产生进位，进位必须带到下一位的计算里。整个算法的主体就是循环做这件事，直到两个链表都走完并且没有遗留进位为止。

那为什么说它“坑不少”？因为很多人写代码时只盯着主循环，忘了处理两个链表长度不一样的情况，也忘了如果最后一位产生了进位（比如 5 + 5 = 10），还需要额外 new 一个节点来存这个最高位的 1。这两点恰恰是LeetCode 判题时最容易卡住的地方，后面我会专门给测试用例。

2. 核心思路：竖式加法怎么翻译成代码逻辑

2.1 用生活化类比理解“逢十进一”

竖式加法是小学内容，但把它翻译成程序逻辑时，很多人反而会被“指针”“节点”绕晕。我习惯做一个类比：想象你在收银台手动加两叠现金，每叠现金按照面额从1元、10元、100元排好，而且你面前正好摆着两个“个位在最前面”的架子。

你从个位开始，把两叠钱的同面额放一起数，如果超过9张，就每10张换一张更高面额的，放到下一轮去数。这个“每10张换一张”就是程序里的carry进位变量。每一次操作只处理当前位的两张（或者一张，如果某一叠已经没了）加上上一轮留下的进位，然后算出“当前位应该写几”和“是否继续进位”。

类比不是跑题，它帮我们锁定代码的核心循环：每一步只做三件事，取值、求和、拆分成“当前位”和“进位”。

2.2 关键变量：carry 进位是如何维护的

代码里最核心的变量就是carry。它的取值只能是 0 或 1，因为两个一位数相加最大是 9 + 9 = 18，加上进位 1 最大也就是 19，所以进位最多是 1。这个观察很重要，它让代码非常简洁：计算当前位之和sum = v1 + v2 + carry，然后val = sum % 10是当前位的结果，carry = sum / 10是下一位的进位。

sum % 10和sum / 10这两个操作，本质上就是在做“逢十进一”的拆解。比如 sum 是 14，那么当前位写 4，进位是 1。很多题解里直接用除法取整，就是因为 carry 只可能是 0 或 1，sum / 10的语义很清楚。

这里还要提醒一下：在 Java 和 C++ 里，整数除法会自动截断小数，所以14 / 10 = 1没问题。但在 Python 里如果直接用/，得到的是浮点数 1.4，必须用整除//。跨语言刷题时，这些细节特别容易“暗算”人。

2.3 为什么要用链表而不是数组模拟

有些读者可能会想：既然逆序存储，我能不能先把链表转成整数，两个整数相加完再转回链表？比如把2 -> 4 -> 3转成 342，算完 807 再转成链表。这个思路在数字比较小的时候确实能跑通，但面试官立刻会追问：如果链表非常长，长到连long都存不下呢？

这正是这道题存在的意义。LeetCode 的测试数据里就有超过 64 位整数范围的大数，你如果把它转成整数，轻则溢出，重则直接报错。正确的做法就是全程模拟竖式加法，不把链表整体转换成数值，而是逐位相加、逐位生成新链表。这也呼应了题目背后的真实需求：大数相加。Java 里的BigInteger、Python 里的int之所以能处理任意大的数，底层思想也跟这题一脉相承——用数组或类似结构分段存储数字，再逐段运算。

2.4 三种情况：两个链表一样长、一长一短、最后还有进位

主循环的终止条件很关键。如果你的循环写成while (l1 != null && l2 != null)，那它会在较短的链表结束后就退出，剩下的高位没人处理。正确的写法应该是while (l1 != null || l2 != null || carry != 0)，只要还有节点或者还有进位，循环就不该停。

我习惯把循环体内的逻辑分成三层：

• 先取数：如果l1不为空，取l1.val，指针后移；否则取 0。l2同理。这一步把“短链表少一位”的情况统一成“补零”。
• 再求和：sum = v1 + v2 + carry，算出当前位sum % 10和进位sum / 10。
• 最后建节点：把当前位的值挂到结果链表的尾部，移动tail指针。

这个“补零”的思路非常像日常对齐小数点：位数不足的地方补 0，让每一轮都能统一处理两个数。你不需要为“l1 走完了”单独写分支逻辑，代码会清爽很多。

3. 实现细节：从零写一个能直接跑的版本

3.1 先搭框架：虚拟头节点为什么能省掉一半的麻烦

链表题有一个非常实用的技巧叫虚拟头节点（dummy head）。因为结果链表是逐步构建的，第一个节点要等第一次求和之后才知道值，如果不用虚拟头节点，我们得单独处理“结果链表为空时”的特殊情况，代码会多很多分支。

ListNode dummy = new ListNode(0); ListNode tail = dummy;

dummy本身不存有效数据，它的next指向真正的头节点。我们只需要让tail不断后移，最后返回dummy.next，就拿到了完整的链表。这个技巧在几乎所有“构建新链表”的题目里都通用，比如合并两个有序链表、链表分区等，建议直接变成肌肉记忆。

虚拟头节点还有一个附带的好处：它让我们能把注意力集中在循环里，不用反复判断tail是不是 null。写出来的代码可读性更高，面试时口述思路也更容易。

3.2 Java版本核心代码逐行讲解

下面直接给完整实现，我用 Java 写，注释尽量详细：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode tail = 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; int digit = sum % 10; carry = sum / 10; tail.next = new ListNode(digit); tail = tail.next; if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; } return dummy.next; }

我们一条条捋：v1和v2用三元表达式做了“补零”，保证不管链表还剩没剩节点，都能安全取值。sum把两个当前位和进位加到一起，digit是最终要写到结果链表上的值，carry是给下一位用的。循环条件里的carry != 0保证了最后一位如果还有进位，会多创建一个节点。if (l1 != null) l1 = l1.next;这行只在链表还没走完时移动指针，避免空指针异常。

这个版本的时间复杂度是 O(max(m, n))，其中 m、n 是两个链表的长度，因为最多循环较长链表的长度次；空间复杂度是 O(max(m, n))，主要花在新链表上。如果面试官问“能不能优化空间”，可以说在允许修改原链表的情况下，可以直接复用较长的链表来存结果，省掉新建节点的空间，但一般不需要在初版就做这个优化，容易引入 bug。

3.3 Python版本：同样的思路，注意整除

Python 版本的代码更紧凑，但有一个容易踩的坑：求和后计算进位，必须用//而不是/。我在前面的章节提过一次，这里再强调，因为这是Python 新手最常犯的错误。

class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode(0) tail = dummy 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 digit = total % 10 carry = total // 10 tail.next = ListNode(digit) tail = tail.next if l1: l1 = l1.next if l2: l2 = l2.next return dummy.next

这个版本跟 Java 版几乎一一对应。total // 10得到 0 或 1，是整除运算；total % 10得到当前位的数字。运行逻辑没有任何区别，但刷题时如果混用两种语言，一定要记住这个语法差异。

3.4 手写测试用例：怎么验证代码是对的

写完代码一定要自己测，不要直接交上去让评测系统打脸。我通常会把测试用例分成四类：

• 基础用例：[2,4,3]加[5,6,4]，对应 342 + 465 = 807。
• 长度不一致：[9,9,9,9]加[1]，也就是 9999 + 1 = 10000，结果链表应该是[0,0,0,0,1]。这个用例同时考验了“短的链表补零”和“循环结束后还有进位”两个点。
• 最后一位进位：[5]加[5]，结果是[0,1]，也就是 10。这个用例专门验证carry != 0作为循环条件的必要性。
• 一方为空：这题说两个链表都非空，但如果你做了防御性处理，可以加一个“链表为空返回另一个链表”的特殊分支，做到更健壮。

手动在纸上推演一遍，代码基本就不会出大错了。别嫌麻烦，我在面试时见过太多人代码写完了，一问他“最后一位有进位怎么办”，当场愣住——这种其实是在考核边界意识，一旦你提前想好，反而成了加分项。

4. 实战变体：当题目换了个马甲，你还能认出来吗

4.1 变体一：正序存储怎么办

题目默认逆序存储，但面试官喜欢追问：“如果数字是正序存储的，比如链表3 -> 4 -> 2表示 342，你怎么相加？”这个变体非常经典，处理方式也很多，我推荐两种：

第一种，反转链表法。先把两个链表反转，就变成了逆序存储，直接复用上面的代码，最后把结果再反转回来。这个方法思路最直接，实现起来也只是多写一个reverseList函数，不容易出错。

第二种，栈法。遍历两个链表，把每个节点的值压入栈，因为栈是后进先出的，取出来的时候正好是从高位到低位再反过来从低位到高位。具体做法是：先把 l1 和 l2 的所有节点值分别压入两个栈，然后从两个栈顶开始同步相加，同样维护carry。因为栈顶是最低位，正好符合从个位开始计算的需求。最后把构建好的链表串起来。

两种方法的时间复杂度都是 O(m + n)，空间上栈法需要额外的栈空间，反转法如果不限制修改原链表也不需要额外空间。我个人偏向栈法，因为它更直观，不需要写反转函数，面试口头解释也容易。但如果你对reverseList已经熟到不能再熟，反转法也完全没问题，挑自己最稳的那个上。

4.2 变体二：改成数组或字符串怎么办

如果把链表换成数组，思路其实换汤不换药：从数组末尾（最低位）开始往前加，维护进位。如果是字符串表示的数字，比如"123"加"4567"，则从两个字符串的末尾逐位取字符，转成数字后相加，处理逻辑跟链表几乎完全一致，唯一区别是每次取值用的是下标而不是指针，循环终止条件是“两个下标都没越界或者还有进位”。LeetCode 第415题“字符串相加”就是这样的题，建议刷完链表版之后顺手把字符串版做一遍，能加深对“模拟加法”这一类题的理解。

数组版还有一个好处：结果可以直接用一个长度等于“较长数组长度 + 1”的数组来存，因为最高位进位的可能只有一个。但实现时需要注意从后往前填数，最后再决定是否要处理掉前导零。这个细节跟链表版的“最后一位进位需要多建一个节点”本质是同一个坑。

4.3 变体三：大数相加与高精度计算的工程应用

很多人会问：我工作里根本用不到手写链表加法，刷这个题有什么用？其实大数相加在工程里非常常见。比如你需要处理超过long范围的整数字符串，直接用语言内置类型会溢出，这时候就需要用“分段存储 + 逐段相加”的高精度思路。Java 的BigInteger、Python 的int内部也在做类似的事情，只是封装成了现成的类。学习这道题，是在理解这些底层工具的原理，而不是在背一道孤立的题。

另一个典型应用场景是金额分账或订单号累加时不能用浮点数，因为浮点数有精度损失。很多金融系统会把金额转成分（整数）来存储和计算，如果金额大到一定程度，同样要考虑大数问题。虽然实际工程大概率会用现成的库，但面试时你能答出“模拟竖式加法的本质就是高精度计算”这一层，就已经比其他候选人高出一个段位。

4.4 变体四：Two Sum 的暴力枚举到哈希表，顺便对比一下

既然热词里出现了“暴力枚举算法”和“两数之和”，这里也做个对比型延伸。Two Sum 的暴力解法是两层循环枚举所有数对，时间复杂度 O(n^2)；优化解法是用哈希表存储“已经遍历过的数字及其下标”，每遍历一个新数，就去哈希表里查“目标值减当前值”是否存在，时间复杂度降到 O(n)。很多初学者不理解为什么哈希表能加速，本质原因是：暴力枚举每次都要从头找，而哈希表能 O(1) 时间完成查找，用空间换时间。

“两数相加”和“两数之和”的相同点是字面上都是“两个数”，但核心技巧完全不同：一个是模拟竖式加法，一个是查找策略的优化。如果面试官把两题连着问，说明他在考察你能不能快速识别题目类型。你需要在脑内自动分类：看到数组反向查找，想哈希表；看到链表逐位相加，想指针遍历 + 进位。这个分类能力比会写某一道题更重要。

5. 面试官追问：这些坑你踩过几个

5.1 最大的坑：忽略最后一个进位

我见过最典型的错误写法是循环条件只写了while (l1 != null && l2 != null)，然后两个链表都走完之后直接返回结果。这种写法在大多数常规用例上能对，但遇到[5]加[5]就彻底错了——个位相加得 10，当前位写 0，进位是 1，可是循环已经结束，这个进位的 1 丢了，返回的链表是[0]，而正确答案是[0,1]（即 10）。

解决的办法就是前面讲到的：循环条件加入|| carry != 0。这个条件从语义上保证了“只要还有数字加，或者还有进位要处理，就继续循环”。这是整道题最核心的边界处理，面试时建议主动说出来，别等面试官提示。

5.2 指针移动的细节：别把 null 移到 next

另一个常见 bug 是访问空指针。比如写完int v1 = l1.val;就直接l1 = l1.next;，如果此刻l1已经为 null，就会出现空指针异常。所以取值前必须判空：int v1 = (l1 != null) ? l1.val : 0;，而移动指针前也要判空：if (l1 != null) l1 = l1.next;。这两个判空不是一回事，前者保证取值安全，后者保证移动安全。二者缺一不可。

还有一种隐蔽的错误：在while循环里，先取了l1.val再移动指针，但l1可能已经在上一次循环结束时变成了 null。我建议把“取值”和“移动”放在同一轮循环里统一处理，不要分开在循环头和循环尾各做一次，否则很容易漏判空。

5.3 测试用例怎么设计才全面

一个合格的算法题测试用例，应该覆盖下面的表：

这张表里的最后一个用例容易被忽略：[0]加[0]。题目说两个链表非空，但没说不可以是单个 0 节点。如果代码里对进位处理不当，可能会多生成一个 0 节点，变成[0,0]。所以测试时不要只盯着带进位的用例，全零用例也能暴露问题。

5.4 复杂度分析怎么答才显得专业

回答复杂度时，不要只背一个结论。我习惯这样表述：“假设 l1 长度为 m，l2 长度为 n，因为每个节点最多被遍历一次，所以时间复杂度是 O(max(m, n))；新链表最多有 max(m, n) + 1 个节点，所以空间复杂度也是 O(max(m, n))。如果面试官要求优化空间，可以考虑复用其中一个链表。”这样不仅回答了复杂度，还展示了你在工程上对空间优化的敏感度，是加分项。

面试官还可能会问“如果链表特别长，比如有10万个节点，会有什么风险”。这个问题其实就是引导你想到大数和高精度，你在第4节积累的内容可以在这里用上：因为算法只遍历一次，10万个节点也只需要 O(n) 时间，但要注意递归写法可能爆栈，所以应该用迭代而不是递归。这里也可以顺势聊聊为什么不用递归实现，因为链表长度可能很大。

5.5 手撕代码时的节奏和习惯

最后讲一点实战经验。真正面试手写的时候，不要上来就敲代码。我的习惯是：先跟面试官确认题目意思，比如“所以数字是逆序存储的对吧”，再说思路，比如“我打算用虚拟头节点，维护一个进位变量，从个位开始逐位相加，循环条件包含进位”，最后再开始写。写的过程中还要主动说边界处理，比如“我会在循环条件里加入carry != 0来防止最后一位进位丢失”。

写完之后千万别急着说“写完了”。花十秒钟检查一遍：有没有处理长度不一致？有没有处理最高位进位？返回的是dummy.next还是dummy？这三个问题只要自检一遍，基本能躲过大部分低级错误。我甚至见过有人返回了dummy本身，结果整个结果链表前面多了一个 0 节点，这是最容易犯的“最后一个节点错误”。

6. 复盘总结：从这道题能带走什么

刷题不能只追求“AC”，每道题都要提炼出可迁移的方法论。这道两数相加，我复盘出三层收获：第一，模拟类问题的通用解法是“找到最小重复单元，翻译成循环”；第二，链表题的核心套路是“虚拟头节点 + 指针移动 + 判空”；第三，边界意识是区分“会写”和“写对”的分水岭，循环条件里多一个carry != 0，就是你比普通选手多想到一层的地方。

如果要把这道题扩展成系列，建议接着刷“字符串相加”“二进制求和”“两数相加 II（正序链表）”，它们共用一个“逐位相加 + 进位”的模板，只是载体从链表变成了字符串或者反过来的链表。刷完这个系列，你再看“大数相加”类的题目，基本就是秒杀。我自己的经验是，把这些题放在同一个专题里集中刷，比散着刷效果好得多，因为相似题之间会互相强化记忆，形成条件反射。

这道题也是一道非常适合写进笔记的题，因为它知识点密集但代码短。你可以把这个解法模板背下来，作为链表模拟题的起点。后面遇到再复杂的题，无非是在这个模板上增加排序、合并或者递归的操作而已。