先把结论放在前头：这道「两数相加」在 LeetCode 热题 100 里的出现频率非常高，但很多人第一反应是“把链表转成整数直接加”，写完一提交才发现溢出。它考的其实不是大数运算本身，而是你愿不愿意接受“链表的每一个节点只存一位数”这种约束，然后用模拟竖式加法的方式逐位处理。
今天这篇就围绕这道题展开，内容包括：为什么这类题不能取巧转整数、模拟加法的核心实现逐行拆解、几个我必须提醒你的坑，以及面试官在追问环节最常问的变化版本。不管你是刚刷题的新手，还是准备面试想查漏补缺，这篇都可以直接拿来当复习提纲。
1. 题目本质：加法进位在链表上的翻译
1.1 先从应用场景说起：为什么需要“大数加法”
现实业务里确实会遇到“数字大到超了 long 范围”的情况。比如某电商平台做交易对账，订单号用雪花算法生成，雪花算法里时间戳加机器号加序号拼出来是一个 64 位以内的整数，虽然没超 long，但如果要处理跨系统的全局唯一 ID，有些方案会直接生成 128 位的数值。这时候你用基本类型去接收就会溢出，必须把数值拆成一段一段来存。
链表存大数，本质上就是“按位拆分”。题目给的是逆序存储，也就是链表的头节点是个位，接着是十位、百位。这种存储方式不是出题人故意为难你，而是和“从低位开始做加法”的人类竖式习惯完全一致。你做加法的时候天生就是从个位开始往高位算，链表也把个位放在最前面，遍历顺序就是计算顺序。
1.2 逆序存储的优势在哪里
如果题目改成“高位在前的正序链表”，实现难度会立刻上升一个档次。因为两个链表长度可能不一样，比如一个三位数加一个两位数，正序时你得先把短链表前面补零，或者先反转链表。而逆序情况下，你从头节点开始走，短的链表走到 null 时，把它当前位的值当作 0 处理就行，完全不用关心谁长谁短。
这就是设计了。链表逆序存储不是噱头，而是为了让你“无脑遍历，缺位补零”。
1.3 把加法拆成三个动作
模拟竖式加法可以拆成三个重复动作：
- 取出链表 l1 当前位的值，如果节点为空则取 0。
- 取出链表 l2 当前位的值，如果节点为空则取 0。
- 计算 sum = 当前位 l1 的值 + 当前位 l2 的值 + 上一次的进位 carry，新节点的值是 sum % 10，新的进位是 sum / 10。
这三个动作用循环包起来，直到两个链表都遍历完。循环结束后，如果 carry 还是 1，说明最高位还有进位，需要额外再创建一个节点。整个过程没有任何高端技巧，就是模拟手工做加法。
2. 核心实现：虚拟头节点与进位传递
2.1 为什么一定要用虚拟头节点
写链表题最容易翻车的就是头节点处理。假设不用虚拟头节点，你需要单独判断“当前节点是不是第一个节点”，如果是，就直接赋值给 result 头指针；如果不是，才让 pre.next 指向这个新节点。这种判断本身不复杂，但会打断主流程的连贯性。
用虚拟头节点之后逻辑就统一了：不管当前是不是第一轮，我都执行 cur.next = new ListNode(...)，然后 cur = cur.next。最后返回 dummyHead.next，就是真正的结果链表的头节点。这个方法在 LeetCode 其他链表题里也通用，比如合并两个有序链表、删除链表的倒数第 N 个节点，都是同一个套路。养成用虚拟头节点的习惯，写链表题会顺手很多。
2.2 循环条件不能写错
核心循环的终止条件是while (l1 != null || l2 != null)，注意这里是||，不是&&。
我用&&写错过一次。场景是两个链表长度不一样，比如 l1 是 3 个节点，l2 是 100 个节点。如果条件是while (l1 != null && l2 != null)，那 l1 走到 null 之后循环直接退出，l2 剩下的一大截全部丢失。虽然测试用例里这种极端长度差不一定出现，但代码在逻辑上就是错的。
正确写法是：l1 不为空就取 l1.val，否则补 0；l2 同理。这样即便一条链表已经走完了，循环依然能继续处理另一条链表剩余的高位节点。
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 dummyHead = new ListNode(0); ListNode cur = dummyHead; int carry = 0; while (l1 != null || l2 != null) { int x = (l1 != null) ? l1.val : 0; int y = (l2 != null) ? l2.val : 0; int sum = x + y + 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; } } if (carry > 0) { cur.next = new ListNode(carry); } return dummyHead.next; } }这段代码里有几个容易忽略的细节。每次取完值要立刻移动指针l1 = l1.next，而且要先判断是否为空。如果 l1 已经是 null，你不能执行l1 = l1.next，会空指针异常。所以移动操作也要放在 if 里面。
2.3 最后一步进位别漏
最高位加完之后如果还有进位，比如 999 + 1 = 1000，循环结束时 carry = 1，这时候必须补一个新节点。这是我最常提醒别人的一个边界点。三个边界条件必须记住：
- 两个链表都为空：循环不进，dummyHead.next 是 null，直接返回 null，符合“0 + 0 = 0”的语义。
- 其中一个链表为空：循环会走完另一个链表的所有节点，相当于直接复制一条链表，只不过中途可能因为 carry 产生新节点。
- 最高位有进位：需要在循环结束后补节点。
测试的时候用一个极端例子：l1 = [9,9,9,9,9,9,9]，l2 = [9,9,9,9]，结果是 [8,9,9,9,0,0,0,1]。这个用例跑通了，说明你的循环终止条件和最终进位处理都没问题。
2.4 一个可运行的完整测试样例
LeetCode 的写法不需要 main 方法，但你自己调试的时候最好能直接跑起来。我一般会写一个简单的 main 方法，把链表的构造和结果的打印都放进去：
public static void main(String[] args) { // l1 = 342 -> 2 -> 4 -> 3 ListNode a1 = new ListNode(2); ListNode a2 = new ListNode(4); ListNode a3 = new ListNode(3); a1.next = a2; a2.next = a3; // l2 = 465 -> 5 -> 6 -> 4 ListNode b1 = new ListNode(5); ListNode b2 = new ListNode(6); ListNode b3 = new ListNode(4); b1.next = b2; b2.next = b3; ListNode result = new Solution().addTwoNumbers(a1, b1); StringBuilder sb = new StringBuilder(); while (result != null) { sb.append(result.val); if (result.next != null) { sb.append(" -> "); } result = result.next; } System.out.println(sb); }输出结果是7 -> 0 -> 8，也就是 342 + 465 = 807。注意结果链表的顺序还是逆序的，第一位是 7，第二位是 0，第三位是 8。
3. 复杂度分析与实战避坑指南
3.1 时间复杂度和空间复杂度到底怎么算
时间复杂度很好算：两个链表各遍历一遍，循环的次数等于较长链表的长度。设 l1 长度为 m，l2 长度为 n，总次数就是 max(m, n)。因为每一位只做常数次操作，时间复杂度是 O(max(m, n))。
空间复杂度有一个容易争论的点。如果你把“结果链表”也算进去，那空间也是 O(max(m, n))。如果面试官问的是“除了返回结果之外的额外空间”，那我用循环写法只用了常数个变量，额外空间是 O(1)。回答的时候我会说清楚：由于答案本身就需要一条新链表存储，整体空间复杂度是 O(max(m, n))，但额外空间只有 O(1)。这么说既不夸大也不含糊。
3.2 我踩过的三个经典坑位
第一个坑：没有提前保存链表头节点。有次我在循环里直接用ListNode head = l1，然后 l1 一直往后走，最后想返回 head，发现 head 指向的链表已经被改动了。因为 Java 里对象引用是传递的，head 和 l1 指向同一块内存。正确做法是：如果你不想改动原链表，就用新节点去构建结果；如果你确实想原地计算，一定要先保存头节点引用，并且清楚原地计算会破坏输入数据。
第二个坑：误把“占位用的虚拟头节点”当成结果返给 LeetCode。你返回 dummyHead 而不是 dummyHead.next，结果就会多出一个 0 节点，在线判题直接报错。这个错很隐蔽，因为本地打印的时候你可能会故意输出 dummyHead.next 来避开，结果提交代码时忘了改。
第三个坑：试图用int sum = Integer.parseInt(listNodeToString(l1)) + Integer.parseInt(listNodeToString(l2))然后再把结果转回链表。这个方案在小数据上是对的，但 LeetCode 给的测试用例专门有一批是几十位的大数，转成 int 或 long 直接溢出。你可能会说那用 BigInteger 行不行，BigInteger 确实不溢出，但题目考察的就是模拟加法能力，你用 API 做出来在面试环境中反而会扣分。
3.3 空间优化思路：能不能原地计算
理论上可以复用其中一条链表，把结果直接写回到 l1 的节点里。这样省去了结果链表的新节点创建，额外空间依然是 O(1)，但“不新建链表”这个点在实际面试中没那么重要，反而会因为你要同时维护三个指针而更容易出错。
比如你复用 l1，就需要一个 prev 指针一直指向 l1 当前节点的前驱，因为当 l1 先走完时，你还要把 l2 剩余的节点借用过来。这种借节点的操作会破坏原始输入的链表结构，LeetCode 判题时通常不在意，但如果你在面试中写了，一定要明确告诉面试官“这个方案会修改输入链表”。我个人的建议是：先写标准的新建节点版本，保证正确性，之后如果有时间再提一句“可以通过原地计算进一步减少新节点创建”。
3.4 递归写法：理解尾递归的另一种视角
这道题也能用递归写，思路是每一层递归处理一位加法，然后把进位传给下一层。递归版本的核心逻辑更简洁，但有一个风险：如果链表很长，递归深度会达到链表长度，可能触发栈溢出。LeetCode 的测试数据一般不会给到那么极端，但本地你拿一条十几万节点的链表去跑递归，大概率会 StackOverflowError。
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return add(l1, l2, 0); } private ListNode add(ListNode l1, ListNode l2, int carry) { if (l1 == null && l2 == null && carry == 0) { return null; } int sum = carry; if (l1 != null) { sum += l1.val; } if (l2 != null) { sum += l2.val; } ListNode node = new ListNode(sum % 10); node.next = add( (l1 != null) ? l1.next : null, (l2 != null) ? l2.next : null, sum / 10 ); return node; } }递归的终止条件是l1 == null && l2 == null && carry == 0，三者同时满足才返回 null。这里很容易写成只判断l1 == null && l2 == null，然后进位丢了。面试的时候我一般会先说递归思路，再用循环实现，因为循环版本更容易向面试官解释指针移动的过程。
4. 面试高频考点与延伸变化
4.1 面试官的追问方向
这道题代码量不大，面试官能追问的点却很集中。最常问的有四个：
第一问：“如果链表很长，你的递归写法是不是有问题？”这个问题其实是在考察你对递归深度和栈溢出的理解。你要答出循环版本不需要额外栈空间，并且能明确说出递归最深可能到几层。
第二问：“假如题目改成返回的链表也要逆序，你怎么处理？”这道题本来就是逆序返回，所以这个问题通常是在考你有没有理解“低位在前”的设定。如果你真遇到返回正序的情况，最简单的思路是先反转结果链表，或者先反转输入链表再用这道题的思路相加。
第三问：“两个数可能非常大，为什么不能转成 int 加？”这个问题就是前面说的溢出问题。你要答出链表长度没有上界，60 位的整数就已经远超 long 的范围，模拟加法是唯一不依赖于数据类型上限的做法。
第四问：“如果输入链表本身就包含前导零，你怎么处理？”比如 [0, 1, 2] 表示 120，第一位是 0。如果你严格按加法做，结果里也可能出现前导零，比如 0 + 0 = 0 会返回 [0]。这个边界通常不需要特殊处理，因为 LeetCode 测试数据默认没有前导零，但知道怎么去掉前导零也算加分项：结果链表上从头部开始跳过值为 0 的节点，直到遇到非 0 节点，最后保留至少一个节点。
4.2 从“两数相加”延伸出去：两数相乘、字符串相加、二进制相加
这道题的套路完全可以迁移到其他题目上。两个字符串相加，比如"123" + "456"，本质上就是从两个字符串的末尾开始逐位相加，维护 carry。只不过链表是直接用指针移动，字符串要用下标索引，逻辑一模一样。
大数相乘会更复杂，核心思路是“错位相乘再累加”。你初始化一个长度为 m + n 的 int 数组，两层循环里每一位相乘的结果加到对应位置上，最后再统一处理进位。这个题目我先不展开，但你要知道它用到的竖式模拟思路，起点就是今天这道两数相加。
还有一道二进制相加，把11 + 1用字符串表示成100。它的加法规则改成逢二进一，sum % 2 是当前位，sum / 2 是进位。理解了十进制加法的进位逻辑，进制变化本质就是模数变化。
4.3 答题节奏：先讲思路再写代码
面试做这道题时，我建议的节奏是：
- 先给面试官复述题目：两个链表代表两个非负整数，逆序存储，返回和的逆序链表。
- 说思路：模拟竖式加法，每一位相加，维护进位 carry，用虚拟头节点统一插入操作，循环结束检查 carry 是否非零。
- 写代码，边写边解释变量含义。
- 给测试用例验证，先给普通用例，再给一个进位极端用例，比如 999 + 1。
这个顺序比上来直接写字码要稳得多。面试官看重的往往不是你写的代码能不能一次通过，而是你能不能把思路说清楚，能不能主动跳到边界条件的测试上。这道题能主动提到“999 + 1 最后会产生额外进位”，就已经赢了一半。
5. 我的个人经验与建议
这道题我至少刷过五次。头两次是在大学时期，当时觉得“这题太简单了”，结果连续踩了循环条件写错和最终进位漏加的坑。第三次是在模拟面试里，被面试官追问“为什么不用 long 直接存”，我支支吾吾答不出来，才真正去理解了逆序存储和模拟加法的设计意图。
我的建议是：把这道题当作链表基础题目的“题眼”，因为它把两个高频考点结合在了一起，一个是对链表指针操作是否熟练，一个是对边界条件是否敏感。你可以不做完整的大数乘法，但一定要能在两数相加上做到闭眼写出来。
如果你真想把这道题吃透，可以自己加练两个变体：一个是把两个链表反转成高位在前再相加，练反转链表的熟练度；另一个是写一个不修改输入链表的原地算法版本，练指针管理的精细度。这两个变体做完，你对链表操作的理解会上一个台阶，而不只是背下一道题的答案。
