企业官网建设流程全解析

hot 100 刷到第 2 题，“两数相加”这关基本上是绕不过去的。很多刚开始刷链表题的朋友会觉得这题不就是把两个链表遍历一遍、把数加起来嘛，实际上里面藏着两个关键点：一是数字按逆序存储，二是进位怎么处理。我最初刷这题时，被“342 表示成 2 -> 4 -> 3”这种反直觉的存储方式绕了几分钟，后来把小学竖式加法在纸上画了一遍才彻底通了——链表头就是数字的个位，从头开始加正好符合人算加法从低位到高位的顺序。这篇文章就结合我自己的刷题过程，把两数相加这道题的思路、代码、边界条件和踩坑经验完整拆一遍，适合刚接触链表的初学者，也适合准备面试、想把这道链表题讲透彻的开发者参考。

1. 题目拆解：hot 100 第 2 题到底在考什么

1.1 输入输出约定与链表结构

题目里的节点定义很标准，在刷题平台里几乎每次都会看到这样一段：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next

每个节点只存一位数字，值域是 0 到 9，通过 next 指针串成一条单链表。输入是两个非空链表，分别表示两个非负整数，而且每一位数字都是按逆序存储的。输出要求也是一个链表，表示两个数相加之后的和，存储格式和输入保持一致。

举个例子，数字 342 在链表里存成 2 -> 4 -> 3，数字 465 存成 5 -> 6 -> 4。把这两个链表相加，得到的结果链表是 7 -> 0 -> 8，对应的数字是 807。这里要注意，结果同样是逆序存储，所以链表头是和的个位，这一点很关键，后面所有思路都建立在这个设定上。

题目还补了一个细节：除数字 0 本身之外，这两个数都不会以 0 开头。这其实是防止出现类似“000342”这种带前导零的输入，算是帮我们排掉了一种边界情况。

1.2 为什么一定要用链表来存数字

不少新手看到这题会有一个疑问：明明语言里有 int、long 这些整数类型，为什么偏要用链表来存数字？直接转成整数相加不就好了吗？

答案很简单：因为题里的数字可能长到超出任何整数类型能表示的范围。比如几百位、上千位的十进制数，别说 64 位整数，就是语言里支持的大整数类型，在某些场景下也会触及上限。链表逐位存储的好处是，每一位只占一个节点，数字有多长，链表就建多长，理论上没有位数上限。所以这题考察的第一个底层认知就是：当数据规模超过基本类型容量时，要用线性结构来逐位表达。

用生活类比来解释的话，就像超市小票上的金额，如果位数很少，我们一眼能读出来；但如果是一串几十位的数字，你更可能选择一位一位地念、一位一位地记，而不是把它当成一个整体去读。链表就是这种“一位一位记”的数据结构。

1.3 逆序存储的巧妙之处

为什么非要逆序，而不是像我们平时写数字那样高位在前、低位在后？

因为链表是单向的，只能从 head 往后走，不能从尾巴往回头。如果数字按正常书写顺序存储，比如 342 存成 3 -> 4 -> 2，那加法要从个位开始算，可个位在最后一个节点，你得先遍历到链表末尾才能开始加。如果是单向链表，这就很尴尬——要么先反转两条输入链表，要么额外借助栈来倒序，代码一下子复杂很多。

反向存储之后，链表的头节点就是数字的个位，从头节点开始遍历，天然满足“从低位加到位”的顺序。这就好比排队结账时，队伍最前面的顾客正好是最低位那位数，你只要从队头一个个处理过去，就能完成整个加法。这个设计不是拍脑袋定的，它是为了让算法实现简单。

2. 解法设计：把竖式加法翻译成代码

2.1 人工计算的三个步骤

先不急着写代码，我们回忆一下小学学的竖式加法是怎么做的。比如 342 + 465：

• 个位：2 + 5 = 7，写 7，进位 0
• 十位：4 + 6 = 10，写 0，进位 1
• 百位：3 + 4 + 1 = 8，写 8，进位 0

结束，结果是 807。

把这个过程抽象成算法就是三件事：第一，从两个链表的当前节点各自取出一个数字，如果某个链表已经走完了，这一位就补 0；第二，把两个数字和上一步留下的进位相加，得到的和对 10 取余就是当前位的值，对 10 整除的结果就是下一步的进位；第三，只要两个链表没走完，或者进位不为 0，就继续重复前两步，同时把当前位生成的新节点挂到结果链表的尾部。

这个流程说起来简单，但它是整道题的核心模型。一旦你把这个“逐位相加 + 进位传递”的模型想清楚，代码怎么写都是对的，区别只是风格的差异。很多人在这一题上写错，不是语法问题，而是脑子里没有一个清晰的手算过程，算法步骤和实际代码对不上。

2.2 虚拟头节点：链表构建的标准范式

写链表构建类题目时，有一个非常常用的技巧叫“虚拟头节点”，也就是 dummy 节点。为什么需要它？

假设我们要从零开始构建一条结果链表，第一节点是在循环里生成的，那在进入循环之前，我们不知道该用哪个节点作为链表的 head。如果没有 dummy，就得先特判第一次循环：要么单独创建一个头节点，再进入循环；要么用“第一个节点是否已生成”这类标记位来控制逻辑。这两种写法都啰嗦，而且容易在边界状态上出错。

dummy 的用法是：先创建一个不参与实际数据的占位节点，让结果链表的游标指针 cur 从 dummy 开始。每次循环生成新节点，就挂在 cur 后面，然后 cur 移到新节点。等你全部处理完，dummy.next 就是真正结果链表的头节点，直接返回即可。

打个比方，这就像你先把一个空盒子摆在工作台上，把结果一个个往里装，最后把空盒子本身扔掉，盒子里的东西就是要交付的结果。这个技巧不仅这一题用得上，合并两个有序链表、删除链表倒数第 N 个节点等很多链表题都能复用。

2.3 进位 carry 的数学本质

进位是这道题最容易出错的地方。每一步我们最多有三个数相加：第一个链表的一位取值、第二个链表的一位取值、上一步传来的进位。由于每一位数字的范围是 0 到 9，进位最大也只能是 1（因为 9 + 9 + 1 = 19）。所以在这道题里，carry 只可能是 0 或 1，不会出现等于 2 的情况。

但这不代表代码里就可以硬编码 carry 为 0 或 1。更稳妥的写法是通用的“整除 + 取余”逻辑：

total = v1 + v2 + carry carry = total // 10 cur.next = ListNode(total % 10)

这样即使以后遇到二进制链表相加（节点值只有 0 和 1），或者每个节点存两位数字（值域扩大到 0 到 99），这套逻辑依然成立，只是进位的取值范围会跟着变化。我见过一些朋友在面试时，因为只记住“carry 是 0 或 1”，结果被面试官追问“如果节点存储的不是一位数字，而是两位数字呢”就卡住了。用 total // 10 和 total % 10 来表达，才是真正理解了这个过程的本质。

3. 完整实现与边界条件解析

3.1 参考代码与逐行注释

直接上一版干净、可复用的 Python 实现。这段代码我用同样的写法在不同题型里改过很多次，基本可以作为模板：

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode(0) # 虚拟头节点，dummy.next 才是结果头 cur = dummy # cur 始终指向结果链表的最后一个节点 carry = 0 # 进位，初始为 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 carry = total // 10 # 更新进位 cur.next = ListNode(total % 10) # 当前位的值 cur = cur.next if l1: l1 = l1.next if l2: l2 = l2.next return dummy.next

这个写法有一个很关键的循环条件：while l1 or l2 or carry。很多初版代码会写while l1 and l2，那样一旦某个链表先走完，循环就停了，另一个链表剩余的高位数字会全部丢失。反过来，用or让循环持续到两个链表都为空、并且进位也清零为止，是最省心的写法。

再看补 0 的策略：当 l1 为空时，取出来的 v1 就是 0；l2 同理。这样两个长短不一的链表对齐了位数，短链表缺失的高位按 0 处理，逻辑非常干净。

3.2 边界情况全图谱

刷题不能只看常规样例，要把所有可能的情况在脑子里过一遍。我按类型整理了一张图谱，方便对照检查：

最高位最终进位这一条最容易被忽略。比如 999 + 1 得到 1000，链表右边要额外多生成一个值为 1 的最高位节点。如果循环条件里漏掉了or carry，这个最高位节点就不会被创建，结果直接变成 000，答案全错。

中间位为 0 的情况也值得强调。比如 99 + 1 的结果是 100，链表中间两个节点都是 0，它们是数字中间的正常位，必须原样保留，不能因为值是 0 就跳过。链表里的 0 是有位置的，位置本身就代表数量级。

3.3 时间复杂度与空间复杂度分析

复杂度的分析要习惯性地做到“主动说清楚”。设两个链表的长度分别为 m 和 n，那么：

• 时间复杂度是 O(max(m, n))，因为我们要遍历两个链表中较长的那个；如果最后有进位，还会多处理一个虚拟的最高位，但这只增加常数操作，整体量级仍然是 O(max(m, n))。
• 空间复杂度要分两个口径。如果不把输出结果链表算进去，只讨论算法运行过程中额外使用的变量，我们只有 dummy、cur、carry、v1、v2 这些固定数量的指针和整数，所以额外空间是 O(1)。如果把结果链表本身也算作空间开销，那么结果链表的长度在 max(m, n) 到 max(m, n) + 1 之间，所以空间复杂度是 O(max(m, n))。

面试时建议主动给出这两句话，尤其是区分“是否计入输出空间”这一点，很多面试官爱听。单纯说“空间 O(1)”其实不够严谨，说“空间 O(max(m,n))”又不够具体，两个口径都提一遍才算完整。

4. 刷题避坑与面试实战

4.1 五个最容易翻车的地方

第一处是循环条件写成while l1 and l2。这个写法在长短不一的链表面前直接崩，长链表剩下的高位节点全丢。我见过的初版代码里，至少有一小半会犯这个错。

第二处是循环条件漏掉or carry。最高位进位处理不了，经典的“999 + 1 = 1000”样例跑出来是“000”，少了最高位的 1。

第三处是最后返回了 cur 而不是 dummy.next。cur 在循环结束时指向结果链表的最后一个节点，如果你把它当成头节点返回，拿到的就是一条残缺链表。检查线上错误时，我看到这个 bug 的频率非常高。解决办法只有一个：记住返回 dummy.next，因为 dummy 才是构建过程的起点。

第四处是先把两条链表转成整数，相加后再转回链表。这种解法在思路上确实最简单，但是数字一旦超过语言整数上限就直接溢出。更关键的是，这题考察的就是链表的逐位操作能力，用整数中转等于绕开了考点，面试官一眼就能看出来。

第五处是直接在原链表节点上修改值。比如有人会把较长链表节点的值原地更新为累加结果，这样确实够省空间，但副作用是修改了输入数据。面试场景下，除非明确允许，否则应该默认保持输入不变，用全新节点构建结果链表。

4.2 测试用例自测清单

写完了代码，别急着提交，先在本地手动跑一遍这些用例。我在实际练习中会固定准备下面几组数据：

用例1: 2->4->3 + 5->6->4 => 7->0->8 用例2: 5 + 5 => 0->1 用例3: 1->8->9 + 3->2 => 4->0->0->1 (981 + 23 = 1004) 用例4: 9->9->9 + 1 => 0->0->0->1 用例5: 0 + 7->3 => 7->3 用例6: 0 + 0 => 0

每组用例都有它要验证的场景。用例 1 是常规带进位的加法；用例 2 验证首轮进位；用例 3 同时验证链表长度不等和连续进位；用例 4 验证最高位进位产生的多一位结果；用例 5 验证一个链表走完后，补 0 逻辑是否正常工作；用例 6 是最简单但也不能忽略的全零输入。

构造测试用例时有个小习惯，建议试试“直接写出结果再反推输入”。比如我先确定结果 1004，再设计 981 + 23，这样能确保用例覆盖到进位链的完整路径，避免测试用例之间相互重复。

4.3 面试追问时怎么接招

这题在面试里出现频率很高，面试官往往在代码写对之后，追加几个问题来看你对题目理解得深不深。

第一个常见追问是：“你能不用额外数组来完成吗？”我们上面的写法本来就是遍历中边读边建，没有用数组缓存，直接回答可以即可。

第二个追问是：“如果链表是正序存储数字呢？也就是说，342 存成 3 -> 4 -> 2，个位在链表末尾。”思路是先把两条链表各自反转，或者用栈把节点值倒出来，变成逆序后再用同样的逐位相加法，最后把结果反转回去。这里关键是要意识到：题目改了一个存储方向，就要想清楚先完成什么预处理，而不是照搬代码。

第三个追问是：“如果每个节点不是存一位数字，而是存两位呢？”进位范围会扩大，但total // 10和total % 10的通用逻辑不变，直接把取余的模数从 10 改成 100 即可。这个问题考的是你是否真正理解了“按位加”的通用性。

第四个追问是：“能不能递归实现？”可以，递归到两条链表的末尾，回溯时计算每一位的和与进位，在回溯过程中逐步构建结果。但递归的缺点是两个链表可能长度不等，代码里需要额外处理补 0 和长度对齐；而且递归深度可能很大，实际工程中不如迭代稳妥，面试时一般提一句即可。

我自己的体会是，面对追问千万不要慌。追问题本质上是给你机会展示理解深度，哪怕一时想不出最优解，能说出“先反转，再算，再反转回来”的完整路径，也比沉默强得多。

5. 从两数相加延伸出去的几种玩法

5.1 解法思想：模拟题的通用方法论

两数相加这道题，本质上是一道“模拟题”——模拟人类已经熟悉的一个计算过程。这类题在算法题单里占的比例不小，包括字符串加法、二进制加法、大数乘法等等。

我自己总结的模拟题套路是三步走：第一步，把人类手算的过程，用白话写成清晰的步骤列表；第二步，把步骤列表里的名词对应到数据结构上，比如“个位”对应链表头，“进位”对应一个整数变量；第三步，把每一步翻译成代码，边翻译边考虑哪些步骤会重复执行，用循环包起来。

很多看起来解法精巧的题，其实并没有那么玄乎。所谓的“优雅解法”，往往不过是你把朴素过程机械化之后，写出来的代码恰好简洁。两数相加就是练习这种“机械化朴素思维”的绝佳素材。

5.2 四个变体思路：正序链表、字符串大数、二进制加法、多链表

这个题模型几乎是各种“大数加法”题的母版。

如果链表改为正序存储，解题方案是先用栈把两串数字倒出来，让个位先出栈，然后完全复用上面的加法逻辑，最后再把结果链表反转或再压栈一次。时间复杂度和原题相同，但栈的空间开销在 O(n)。

如果题目变成“两个字符串表示的大数相加”，本质也是从字符串末尾（个位）开始，逐位取字符转数字，相加后把结果字符插入结果字符串头部。代码长得和链表版完全不同，但核心思路完全相同。我当时为了练习，把链表版改写成了字符串版，等于用两遍书写巩固了同一个模型。

如果题目变成“二进制链表相加”，节点取值只有 0 和 1，仍然是 total // 2 和 total % 2 的套路，循环条件依然是while l1 or l2 or carry。你甚至可以现场推导一遍：最大 total 是 1 + 1 + 1 = 3，carry 依然是 0 或 1，结论完全闭环。

如果题目变成“k 条链表同时相加”，则需要每轮同时取 k 个节点的值求和，再统一处理进位。这样一轮就能处理完所有链表的一位，而不是两两合并 k-1 次。这道题的扩展方向很多，抓住“逐位加 + 进位传递”这个内核，就能以不变应万变。

5.3 顺带刷哪些链表题最省力

链表题不适合按难度从易到难硬刷，更适合按技巧分类刷。两数相加练完，接着刷下面几类题会特别顺：

• 合并两个有序链表：同样用到双指针遍历和虚拟头节点，代码结构几乎一模一样，只是把“加法”换成了“比较大小”。
• 反转链表：这是链表题最基础的操作之一，正序存储加法的预处理就靠它。
• 删除链表的倒数第 N 个节点：用虚拟头节点加双指针，很典型的快慢指针应用。
• 排序链表去重：同样需要遍历链表并维护前置指针，指针操作的熟练度能在上面几题中充分积累。

把这类共享相似技巧的题放在一起刷，效率比按题号顺序刷高得多。我刷链表专题时，习惯在笔记本里按“虚拟头节点”“双指针”“原地反转”这样的小标签给题目分类，每类攒几道题，等到面试前翻一遍，思路非常清晰。

最后分享一个小经验：刷两数相加这道题，不要在提交通过之后就走人。我见过很多人一次性写出了正确代码，但复盘时却说不出为什么用 dummy、为什么循环条件是 or 而不是 and。真正的收获来自“讲得清”，而不是“写得对”。我自己练习时，每次写完会给旁边的人讲一遍整体流程，讲不清楚的地方，就是理解还没到位的地方。把这道题吃透，链表题的内功至少能夯实一大半。