企业官网建设流程全解析

100 题计划推进到第 2 题，题目编号恰好也是 LeetCode 的第 2 题：两数相加（Add Two Numbers）。本来以为第二题还在热身区，结果上来就是一道路径清晰的链表题，还带着"进位"这个经典难点。这一题让我第一次意识到，刷题不是拼手速，而是拼能不能像机器一样一位一位处理数据、能不能把所有边界情况想完。

题目解决的事情非常直观：两个非空链表分别表示一个整数，数字按逆序存放在每个节点里，要求把两个数相加，并且把结果同样用链表返回。应用场景也很真实——大数相加在计算器、底层算术库、金融系统里都遇到过，现实中不会用链表存大数，但这道题考的是链路遍历、节点创建、进位传递这一整套基本功。不管你是准备面试、巩固数据结构，还是单纯想提升代码手感，这题都值得花时间慢慢啃。

我把完整拆解过程、循环和递归两种实现、边界条件踩坑记录以及复盘模板一并写出来，希望能帮你少走弯路。

1. 先搞清楚这道题到底在考什么

1.1 题目说人话版本

LeetCode 原题描述比较官方，我用大白话翻译一遍：给你两个链表，比如2 -> 4 -> 3表示整数 342，5 -> 6 -> 4表示整数 465。链表是倒着存的，头节点代表个位。要求返回一个新链表表示两个数相加的结果：342 + 465 = 807，所以要返回7 -> 0 -> 8。每个节点的值只能是 0 到 9 的单个数字，输入链表不为空，并且整数没有前导零。

最反直觉的地方就是"逆序存储"。为什么单链表要这样存数字？因为两个整数相加，数学上最自然的顺序是从个位开始，而单链表从头节点出发是最高效的。逆序存储让"头节点 = 个位"刚好对齐了人工竖式运算，所以这道题本质上是让你用代码模拟一次列竖式。

有些人会疑惑，为什么不用数组或者直接转成整数？题目偏偏选链表，是因为链表节点天然适合"逐位生成结果"的场景：你每计算出一位，就 new 一个节点挂上去，不需要预先知道结果有多长。这个特性是数组做不到的，也正是面试官想看到的理解深度。

1.2 隐藏在题目里的三个考点

第一个考点是链表遍历。你必须在 O(n) 时间内同时走完两条链表，并且清楚什么时候该停。很多新手会先想"算两个链表的长度"，但这题根本不需要，因为两个链表可能等长，也可能一长一短，你要做的是边遍历边相加，走到两条链表都结束、并且没有残余进位为止。

第二个考点是进位处理，这是全题核心。个位相加满 10 要进 1，十位相加要把这个 1 加上来。进位还会导致结果链表比两个输入链表都多出一位，比如5 -> 5加5 -> 5，结果是0 -> 1 -> 1，最后那个新节点就是进位创建出来的，最容易漏掉。

第三个考点藏在细节里：不要修改输入链表。很多人图省事，直接在原链表上改值，实际工程里这会污染调用方的数据。我一开始就养成了"新建输出链表"的习惯，后面做各类链表题时被证明非常有用。

2. 思路推进：从最直觉的解法到真正能过的解法

2.1 第一反应：转成整数算完再拆回去，为什么行不通

第一次看到这题，我的第一反应是：把链表遍历一遍，拼成数字，相加，再转回链表。思路非常简单：读两个链表得到两个 int，相加，然后每次ans % 10取余数建节点，ans //= 10继续拆。这个方案写完能跑通示例，但它是典型的"看似对的错误答案"。

第一，整数溢出。真实评测里链表可以有几万个节点，对应的数字早就超出 int、long 的表示范围。Python 的大整数能撑住，但 C++、Java 会直接溢出，算出一个错误的哈希值或者异常值，然后整道题分分钟被打回。第二，面试官绝对不会满意，因为这题想考的是指针操作，你用语言特性绕过去了，完全没展示出数据结构功底。第三，先转整数的过程本来就要额外遍历，时间和空间都比直接模拟竖式差，属于既笨又不讨好的解法。

2.2 正确姿势：模拟人工竖式

回到小时候算 342 + 465 的场景。你会从个位 2 + 5 写 7，十位 4 + 6 写 0 进 1，百位 3 + 4 + 1 写 8。这个流程翻译成代码就是四句话：

• 维护一个进位变量carry，初始为 0；
• 同时从两个链表头节点出发，取当前节点的值，某条链表走完了就按 0 处理；
• 当前位和 = n1 + n2 + carry，新节点值 = sum % 10，进位 = sum // 10；
• 两条链表都走完并且 carry 为 0 时，停止循环。

这个思路最大的好处是，完全不需要知道两条链表谁长谁短，"短链表走完了就补 0"这一招天然吸收了长度差。我建议你在纸上手动走一遍9 -> 9 -> 9+1这个例子，看看能不能推出0 -> 0 -> 0 -> 1。如果能独立走通，思路就基本通了，后面写代码只是在翻译这个过程。

2.3 dummy node 是这道题最大的工程技巧

链表题里"头节点可能变化"的场景特别多。相加的结果可能是空节点吗？这题输入非空且结果至少是 1，所以结果链表不会为空，但结果的位数可能比两个输入链表都长，也可能因为"只有进位新增了一位"导致新节点并不好预先确定。如果不引入 dummy node，你就必须写if result_head is None来判断当前新节点是不是第一个，代码又长又容易漏。

dummy node（哑节点、哨兵节点）的思路是：先创建一个不存真实数据的节点，让所有新节点一律挂在 dummy 后面，最后返回dummy.next。这样第一个真实节点和后续节点的插入逻辑完全统一，不需要任何特判。我第一次没预习、直接硬写，代码里塞了三个 if 分支，丑且容易错；第二次老老实实加了 dummy，核心循环压缩到十几行，思路也清爽了。链表的很多经典题，比如合并有序链表、删除倒数第 n 个节点，都能复用这个技巧，建议你把它当成一种条件反射。

3. 完整实现：循环版和递归版一起讲透

3.1 循环版：我推荐所有人都先掌握这个版本

下面是 Python 3 的实现，注释我给得非常详细，直接抄作业也没问题。

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def add_two_numbers(l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode(0) # 哨兵节点：不存真实数据，只为了统一头节点处理 current = dummy # current 永远指向结果链表的尾部 carry = 0 # 进位，只能取 0 或 1 # 只要还有节点没走完，或者还有进位要处理，就继续循环 while l1 is not None or l2 is not None or carry: v1 = l1.val if l1 is not None else 0 v2 = l2.val if l2 is not None else 0 total = v1 + v2 + carry current.next = ListNode(total % 10) # 当前位只保留个位 carry = total // 10 # 十位作为进位 if l1 is not None: l1 = l1.next if l2 is not None: l2 = l2.next current = current.next return dummy.next

几个需要展开的细节，都是我自己踩过之后才理解的：

• 循环条件while l1 is not None or l2 is not None or carry。我第一个版本写的是while l1 and l2，结果在"一个链表走完、另一个还没走完"的用例上报错，因为循环提前退出，后半截根本没加进去。把两个链表都放进条件，再把 carry 也放进去，才能覆盖所有情况。carry 放在循环条件里的价值体现在9 -> 9+1这种用例上：两条链表走完后 carry 还是 1，如果不判断 carry，最后一个进位节点就会丢。
• v1 = l1.val if l1 is not None else 0这种"取不到就补 0"的写法，是处理长短链表差异的核心。有人会先求长度再对齐，完全没必要，补 0 让两边的处理逻辑对齐，代码也少掉一堆分支。
• 新节点只存total % 10，进位只存total // 10。这里 total 最大是 9 + 9 + 1 = 19，所以 carry 只有 0 和 1 两种情况，但写total // 10依然比写if total >= 10再减 10 更通用，也更不容易出错。

3.2 递归版：换个角度理解递推关系

递归思路和循环完全等价，但能把"补 0 + 进位"的递推关系看得更清楚：每一层只负责处理一个节点，然后递归处理 next 节点，同时把新的进位传下去。

def add_two_numbers(l1: ListNode, l2: ListNode, carry: int = 0) -> ListNode: if l1 is None and l2 is None and carry == 0: return 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 node = ListNode(total % 10) next_l1 = l1.next if l1 is not None else None next_l2 = l2.next if l2 is not None else None node.next = add_two_numbers(next_l1, next_l2, total // 10) return node

递归版最大的优点是代码短，逻辑定义非常清晰；缺点是当链表很长时，递归会占用 O(n) 的调用栈空间，严格来说空间复杂度比循环版更差。循环版除了结果链表外只需要常数个变量，额外空间可以理解为 O(1)；递归版因为调用栈，额外空间是 O(max(m, n))。如果面试时面试官要求"不要使用额外递归栈"，你就得当场把递归改成循环。我建议循环版背熟，递归版用来验证自己对递推关系的理解，实际提交优先循环版。

3.3 时间和空间复杂度到底是多少

时间上，每个节点最多被访问一次，所以时间复杂度是 O(max(m, n))，m 和 n 分别是两个链表的长度。空间上，答案链表的长度是 max(m, n) 或 max(m, n) + 1（取决于最后有没有进位），所以空间复杂度也是 O(max(m, n))。很多人在写完代码后觉得"这题这么简单，复杂度随便写写就行"，结果被面试官追问一句"为什么答案链表可能比输入长一位"就卡住了。这里的答案就是：最后一位进位会额外创建一个节点。

复杂度分析不是交差用的，它能帮你反推代码是否正确：如果答案链表长度允许比最长输入链表多 1，那么你的代码里必须有"循环结束前创建最后一个节点"的逻辑；没有这个逻辑，复杂度上就埋着 bug。

4. 边界条件与实战踩坑记录

4.1 一份可以直接拿去自查的边界清单

我把这道题值得单独跑一遍的用例整理成表格，强烈建议写完代码后对照着测：

这 6 种情况基本覆盖了所有长度与进位的组合。实测下来，最常见的漏是第四种"最后多出来的进位节点"，其次是第二种"连续进位导致前一个节点也受影响"。每写完一遍代码，我会把这张表从头到尾跑一遍，跑完再提交，能把提交次数从七八次压到两次以内。

4.2 我真实踩过的几个报错

第一个报错是 NullPointerException / AttributeError。原因是在 while 循环里写了while l1，短的链表先走完，循环直接停了，后半截没加进去。解决方式就是前面说的，把条件改成三种情况的或关系：while l1 is not None or l2 is not None or carry。

第二个报错是结果"多了一位"或者"少了一位"。少一位是因为最后 carry 为 1 时没有新建节点；多一位则反过来，可能是在某个分支里把 0 节点当成进位节点重复插入了。这里有一个小技巧：不要一边循环一边在while条件里移动指针，而是统一用if l1 is not None: l1 = l1.next的写法，这样代码的每一步都是显式的，不容易错位。

第三个问题比较隐蔽：我一开始想直接把结果覆盖到 l1 上，判断完"l1 比 l2 长"还是"l2 比 l1 长"之后的代码越来越复杂，最后连续改出两个 bug。后来我彻底放弃原地修改，改用 dummy + 新建节点，代码一下子简单了。链表题第一要务是保证正确，再考虑节省空间；除非题目明确要求原地修改，否则新建结果链表永远是最稳的方案。

5. 从一道题到一类题：我把这次刷题讲透

5.1 每次刷完题，我用这个复盘模板

很多人刷题是"写完 AC 就关页面"，下一次遇到类似的题依然不会。我从这道题开始强制自己用下面的模板做复盘：

• 这道题属于哪类题型？（链表、双指针、动态规划、前缀和……）
• 核心技巧是什么？（本题：哨兵节点 + 模拟竖式）
• 我想出最优解花了多久？卡在哪里？（第一次卡在"会不会溢出"，第二次卡在"最后一位进位"）
• 如果把链表换成数组或字符串，题目会变成什么？
• 能不能把核心技巧翻译成一句口诀？（我的口诀：一位一位加，够十就进一，短了补 0，最后别漏 1。）

这套模板最多花五分钟，却能把一道题的价值放大好几倍。刷到 100 题的时候，你会发现自己无形中建了一个"题型 -> 技巧 -> 用例"的索引，看到新题能快速匹配旧题，而不是每次从零开始。

5.2 这道题能迁移到哪些同类型题目

两数相加的底层模式，是"两个线性结构的逐位合并 + 进位/借位的状态传递"。这一类问题至少有四种变体：

• 合并两个有序链表：同样是遍历两条链表，只是合并规则从"相加"变成"比较大小"；
• 字符串形式的大数相加：把链表换成字符串，逐位相加，处理方式和本题完全一致；
• 二进制字符串相加：把十进制改成二进制，进位从"满 10 进 1"变成"满 2 进 1"；
• 多项式或者稀疏数组相加：思路依然是"逐项合并 + 系数相加"。

你会发现链表题很少是孤立知识点，各种技巧都是互相套用的。今天把 dummy node 用顺了，明天做"删除倒数第 k 个节点"时自然就会想起它。刷题本质上是在积累"可迁移的模式"，而不是在背题。

5.3 100 题计划的节奏与心态建议

这是我在计划推进到第 2 题就想单独说的建议：不要追求一天刷很多题，要追求每一题真的消化。我给自己定的标准是：新题先独立思考 20 分钟，想不出再看题解；看懂题解后，合上答案自己复写一遍；复写通过后，再用 5 分钟把复盘模板填完。一道题从看题到复盘控制在 60 分钟以内。

节奏上，前期建议按题型刷，比如这周全是链表，下周全是栈与队列。同一个技巧在不同题里反复出现，第二次见到时你已经开始有肌肉记忆。我的 100 题计划大致这样安排：前 30 题覆盖链表、哈希表、双指针这些高频基础结构；中间 40 题覆盖二叉树、回溯、动态规划这些进阶内容；最后 30 题随机混刷，检验综合能力。这个进度不快，但非常稳。

最后说一点个人体会。100 题计划里，第二题就让我意识到一个很扎心的事实：看别人题解觉得"我懂了"，和你亲手写出来、被测试用例打回来两次之后真正改对，中间差着十万八千里。这道题最难的其实不是算法，而是静下心来把边界想完。我后来每次提交前都会强迫自己过一遍那 6 个边界用例，这个习惯帮我省下了大量反复提交的时间。如果你也在刷题计划的前期，建议和我一样先把第二题这种经典题彻底吃透，后面的路会顺很多。