企业官网建设流程全解析

LeetCode 2. 两数相加，是我这几年带新人刷题时几乎每轮都会聊到的一道链表题。题面看起来特别简单：两个链表分别存储一个非负整数的每一位，而且是逆序存的，你把它俩加起来，返回一个新的链表。可是很多人在纸上画两下觉得“哦这不就是模拟加法嘛”，结果一到敲代码就卡住，不是指针串飞了，就是忘掉最后那一个进位，再要么不知道链表长度不一样该怎么优雅处理。今天我想把自己的解法、踩过的坑、以及怎么把这类进位模拟的题目真正写熟练的思路完整摊开来讲，希望能对正在啃链表题的你有实质帮助。

先说结论：这道题真正训练的就三件事，第一是链表指针操作的基本功，第二是进位怎么用变量传下去，第三是边界条件怎么想全。这三件事放到企业开发里也照样常见，所以它才是经典，不是因为它难，而是因为它覆盖了最容易被忽视的基础细节。

1. 这道题到底在考什么：从题目本质拆解解题思路

1.1 逆序存储是“故意”的，还是难点伪装

很多第一次做这题的人都会觉得逆序存储很别扭，忍不住想先把链表转成整数，算完再转回链表。其实逆序存储不是出题人故意刁难你，恰恰相反，这是在帮你降低实现难度。

我们平时手算多位数加法，一定是从个位开始，一位一位往左加，逢十进一。链表从头节点开始就是最低位，意味着你拿到 l1 和 l2 的第一对节点时，不需要做任何倒序处理就可以开始模拟个位相加。这个设计非常天然：你只需要从头往后同步遍历两条链表，每走一步就是当前位，加完就把进位带向下一位即可。

反过来说，如果题目把数字改成“正序存储”，那才是真正的难点。因为链表只能单向遍历，你就不方便从个位开始加，需要先想办法把链表反转，或者用栈保存，整体复杂度会明显上升。所以看到逆序存储，应该感到庆幸，它直接替你拆掉了最麻烦的一环。

我在实际教学里发现，很多人被误导性的“先转整数”方案带偏，是因为他们不熟悉链表操作，总想着回到自己更熟悉的整数世界里。一旦遇到很长的链表，比如几千个节点，转成整数后早就溢出 long long 范围了，这条路根本走不通。除非题目明确说明数字范围很小，否则千万别走转换的路子，直接用链表模拟才是正解。

1.2 两种朴素思路的取舍：先把链表转成整数 vs 直接模拟

先说“先把链表转成整数”的思路。它的操作流程是：遍历 l1，每次把当前节点值乘上 10 的幂次然后累加，得到 num1；同理得到 num2；两者相加得到 sum；再把 sum 不断取模和除以 10，拆成一个个数字，创建链表节点串起来。这个思路在数学上完全正确，代码也确实好写。

但它有严重的工程问题。第一个问题就是溢出：链表的长度上限在 LeetCode 上可以到 100 甚至更长，一个 100 位的整数远超所有内置整数类型能表示的范围。即便题目没说链表多长，你也不能依赖 int 或 long long。第二个问题是效率：转换本身需要多次乘法和取模，和直接模拟加法相比多了无谓的计算。第三个问题是它违背了链表题目的训练意图：这题真正想让你练的是链表遍历、节点创建、指针连接，而不是整数运算。

直接模拟的思路就清爽得多：定义一个新链表的虚拟头节点，然后同时遍历 l1、l2，每个节点取出来相加，再加上进位的值。当前位的结果用 sum % 10 得到，进位用 sum / 10 得到。只要两条链表还没走完，或者进位还不为 0，就继续创建下一个节点。这个方案不依赖数字长度，没有任何溢出风险，而且时间复杂度和链表长度完全线性。

所以我的建议非常明确：做链表题，优先用链表的思维去思考，不要总想“先转成别的数据结构”。这不仅是为了通过这道题，更是为了养成一种数据结构敏感度。

1.3 时间复杂度与空间复杂度的初步判断

在动手写代码之前，先想清楚复杂度。这个习惯看着不起眼，但能帮你在写完后校验自己的实现是否合理。

直接模拟方案中，两条链表各遍历一次，最坏情况是较长那条链表的长度，记为 n。进位处理只需要常数时间，因此时间复杂度是 O(n)。空间方面，新链表每个节点对应结果的一位，结果长度最多是 max(len1, len2) + 1，所以空间复杂度同样是 O(n)，当然这里不算 l1、l2 本身占用的空间。

如果采用“先转整数”方案，时间上要遍历三次，空间上同样要额外构造结果链表，还多出潜在溢出风险，显然不如直接模拟优雅。这也是面试中常被追问的：能不能做到常数空间？可以，但前提是允许修改输入的链表，或者复用其中的节点。LeetCode 这题一般不要求原地操作，所以创建一个新链表是最清晰也最稳妥的。

2. 链表和进位：两个决定成败的细节

2.1 头节点、移动指针和“尾插法”的误解

链表的操作无非就是“改指针”，但因为指针本身也是变量，初学者经常混淆“保存头节点”和“移动指针”这两个概念。比如创建一个新链表时，很多人会直接写一个 head = NULL，然后每次循环里让 head 指向新节点。这样操作完，最后 head 已经跑到链表尾部了，头节点丢了。

正确的做法是维护两个角色：一个是头节点或者虚拟头节点，用来在最后返回时找到链表入口；另一个是游标指针 current，负责永远指向当前链表的尾部，方便直接追加新节点。每一次创建新节点，先让 current->next 指向它，再把 current 移过去，这样头节点始终稳定。

一个特别实用的技巧是在链表头前加一个虚拟节点。这个虚拟节点的 val 可以随便填，它的作用是让代码里不需要特判“第一个节点时指针为空”的情况。比如：

struct ListNode dummy; dummy.next = NULL; struct ListNode *cur = &dummy;

之后每次只需要 cur->next = new_node; cur = cur->next; 就能依次追加，最后返回 dummy.next 就是真正的头节点。这段代码比我以前写的“初始时 head = NULL，再 if (head == NULL) head = new_node else 遍历到尾节点”干净得多，逻辑上也少一个分支。

2.2 进位的完整生命周期：sum % 10 与 sum / 10

进位是这道题的灵魂，也是一个容易在第一次写时理解不透的概念。模拟加法时，每一轮我们把当前位的两个数字和上一位来的进位加在一起，得到一个总数 sum。知道了总数，当前位写什么就显而易见了：对 10 取余，因为每一位数字只能是 0 到 9。下一位要带多少进上去？整除 10 就可以。

举个例子，假设某一位是 8 和 5，上一位进位是 0，那 sum = 13，当前位就是 3，进位是 1。再下一轮如果链表还有节点，就继续加 1。如果两个链表都走完了，进位还是 1，那就需要在结果链表的末尾多创建一个值为 1 的新节点。

很多人容易忘记的是：l1 或 l2 已经为 NULL 后，它们的“当前位”应该当作 0 参与运算，而不是让整个循环停掉。比如 999 + 1，l2 只有一位，但 l1 还有两位要走，这时 l2 为 NULL，就相当于一直加 0。如果循环条件写成 while (l1 != NULL && l2 != NULL) 且没有额外的处理，那么 9 + 1 之后不会继续处理剩余位，直接就返回错误结果了。

2.3 长度不对称时的处理：循环条件用 or 而不是 and

这一节我想单独拎出来强调，因为太多人在这里翻车。两个链表长度不一样时，有两种处理思路。

第一种是先把两个链表遍历到等长，比如哪个更长就先走几步，但代码不好写，而且还要维护偏移量。第二种是更直接的思路：让循环一直走，直到两个链表都为空并且进位为 0 才停止。在循环体内部，用 if 判断当前链表是否为空，不为空才取值并移动指针。

核心循环结构如下：

while (l1 != NULL || l2 != NULL || carry != 0) { int sum = carry; if (l1 != NULL) { sum += l1->val; l1 = l1->next; } if (l2 != NULL) { sum += l2->val; l2 = l2->next; } // 创建新节点，值为 sum % 10 // carry = sum / 10 }

这样的好处是：长度差自动被“补零”的思路吸收掉了，进位 0 也自然让循环在合适时机结束。代码可以只写一个循环，不用拆分成“处理公共长度”和“处理剩余长度”两段。

我最开始学这题时，习惯先求两条链表长度，再区分长短分情况处理，代码看起来比现在复杂一倍，还容易在拼接剩余部分时忘了把进位加进去。后来意识到 or 条件加内部判断才是这个问题的标准解法，清爽又不容易错。

3. 用 C 语言完整实现：代码走查与边界处理

3.1 从零写节点创建与辅助函数

C 语言写链表题，首先要处理的是节点分配。LeetCode 的题目里已经定义了结构体：

struct ListNode { int val; struct ListNode *next; };

我们要在代码里手动 malloc 新节点，然后对 next 指针赋值为 NULL。这个步骤不能省，否则可能出现未定义行为。我在本地调试时经常犯一个错：malloc 完节点后忘了给 next 赋 NULL，结果链表尾部指向一块未知内存。在 LeetCode 的测试环境里不一定每次都崩，但一旦链表被继续遍历就会出问题。

为了代码更干净，我会写一个很小的辅助函数 createNode：

struct ListNode* createNode(int val) { struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode)); node->val = val; node->next = NULL; return node; }

这个函数看着平凡，但能让主循环里少两行初始化代码，也让逻辑更清楚。尤其面试时，你可以在白板上直接说“我封装一个节点构造函数”，考官会认为你代码组织能力在线。

3.2 核心 while 循环的三种写法对比

很多人喜欢在主循环前先把 l1 和 l2 的第一位单独处理，然后再进入循环，理由是这样能保证头节点一定存在。但这个做法会让第一个节点和后续节点的逻辑不一致，还容易漏掉“第一位就有进位”的情况。我更推荐用虚拟头节点统一逻辑。

在写核心循环时，常见的实现有三种。第一种是 while (l1 != NULL || l2 != NULL)，循环结束后再单独判断 carry 是否非 0。第二种是把 carry 也写进循环条件，也就是 while (l1 != NULL || l2 != NULL || carry != 0)。第三种是用递归。

从实际反馈看，第二种最直观。因为进位本身就是待处理的“数值”，把它当作循环条件的一部分非常自然。第一种也不难，但容易在循环外忘记处理最后的进位。递归写起来比较优雅，但 LeetCode 的链表可能很长，递归层数一深会有栈溢出风险，所以我个人不建议在生产环境或面试中优先使用。

核心循环实现：

while (l1 || l2 || carry) { int sum = carry; if (l1) { sum += l1->val; l1 = l1->next; } if (l2) { sum += l2->val; l2 = l2->next; } cur->next = createNode(sum % 10); cur = cur->next; carry = sum / 10; }

写到这一步，其实整个题已经完成大半了。

3.3 善后处理：最后一轮进位怎么补

最后一个进位的处理是高频失分点。比如 5 + 5 = 10，两条链表都是单节点，循环执行完第一轮后，当前位是 0，carry 是 1。如果你用“先循环后处理 carry”的写法，一定要记得循环外判断：

if (carry) { cur->next = createNode(carry); }

而如果把 carry 写进循环条件，最后一轮循环自动会多执行一次，创建值为 1 的新节点，不需要额外写补救代码。

我建议用后一种方式，因为它的逻辑自洽：只要还有进位没处理完，就要继续创建节点，直到进位为 0 为止。这也能避免“最高位多出一个 1”的漏网之鱼。这道题我在本地测试时，最喜欢键入的测试用例就是 [9,9,9] + [1]，因为这一条用例把长度差、逐位进位、最终进位全部覆盖到了。

3.4 完整源码（可直接提交）

下面是我最终整理的版本，代码风格偏工程化，函数拆得比较细，方便阅读也方便测试。

#include <stdlib.h> struct ListNode { int val; struct ListNode *next; }; struct ListNode* createNode(int val) { struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode)); node->val = val; node->next = NULL; return node; } struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { struct ListNode dummy; dummy.next = NULL; struct ListNode* cur = &dummy; int carry = 0; while (l1 != NULL || l2 != NULL || carry != 0) { int sum = carry; if (l1 != NULL) { sum += l1->val; l1 = l1->next; } if (l2 != NULL) { sum += l2->val; l2 = l2->next; } cur->next = createNode(sum % 10); cur = cur->next; carry = sum / 10; } return dummy.next; }

注意这里 dummy 是栈上变量，我们返回的是 dummy.next，它指向堆上分配的节点，所以函数结束后 dummy 本身销毁没有影响。这个方法非常干净，不需要为 dummy 单独 malloc，也免去了最后需要 free(dummy) 的麻烦。

不过这里也有个小争议：LeetCode 的判题系统不会帮我们检查这块内存的释放，而在真实工程中，malloc 出来的结果链表需要调用方负责释放。在刷题场景下，一般不要求释放结果链表，但如果在练习代码时自己写 main 函数做测试，我建议把 createNode 里创建的每个节点都跟踪释放。

4. 实际调试中踩过的坑与排查清单

4.1 返回头节点还是尾节点：一个低级但常见的错

我在带人调试时发现，最容易发生的不是算法错，而是函数结尾写错。有人会把 cur 节点返回出来，因为 cur 一直是“当前处理到的节点”，看起来最自然。但 cur 在循环结束时指向的是结果链表的最后一个节点，返回它，就相当于把整个链表的头丢了。正确的一定是返回 dummy.next，或者单独保存的 head 指针。

如果你没有用哑节点，而是手工维护 head 和 tail，最容易出的错就是“第一个节点创建时 head 不为空”的条件写反了。我建议统一使用 dummy 指针，从根上消除这类低级问题。

另外一个相关的小坑是：在循环里创建节点并让 cur 后移后，忘了把新节点的 next 初始化为 NULL。虽然 createNode 里面已经处理了，但如果你偷懒直接在循环里 malloc，就很容易忘。一旦 next 是随机值，最后返回的链表在某些环境下看起来长度“多了一位”，排查时极其痛苦。

4.2 空链表、单个节点、长链表：边界用例要提前列

LeetCode 的测试用例当然会覆盖各种边界，但你自己写代码时也要形成列边界用例的习惯。对这道题来说，我觉得这几个用例是必须验证的：

• l1 为空，l2 为 [1,2,3]，结果应该和 l2 完全一致。
• l1 为 [5]，l2 为 [5]，结果应该是 [0,1]，因为 5 + 5 = 10。
• l1 为 [9,9,9]，l2 为 [1]，结果应该是 [0,0,0,1]，覆盖长度差和连续进位。
• l1 和 l2 都为 NULL，结果应该是 NULL。这在题目描述中可能不出现，但标准解法用 while 条件加上 carry 判断，其实也能正确处理。

把这些用例列清楚，再对着代码逐行走一遍，基本就能确认逻辑没有问题。尤其在用手写板或者白板写代码时，这种“干跑用例”的能力非常加分。

我在本地写完代码后，总是会顺手调一个可执行的小测试程序，不依赖 LeetCode 平台。比如自己构造三条链表，然后打印结果链表的每一节点。这个测试程序写起来很简单，但能帮你快速定位问题，不必等提交后才被系统打回。

4.3 关于 malloc 失败与内存释放的谨慎提醒

C 语言面试题很少会聊内存释放，但真实项目中必须考虑。线性分配大量小节点时，理论上 malloc 有可能失败。刷题时可以忽略，但如果你要在工程代码里使用类似逻辑，最好加上对 createNode 返回值的判断。当然，LeetCode 环境里这样写反而显得代码臃肿，所以在实际提交前我会把函数的简洁性放在第一位。

内存释放方面，我建议在本地测试时写 cleanup 函数。遍历结果链表并一个个 free，同时也要注意不能 free 掉输入链表本身。如果题目允许复用节点，那内存策略就更复杂了。我在写这道题时，用新节点构建结果链表，原链表不动，所以释放逻辑完全不会影响输入。

不要因为刷题不检查内存泄漏，就养成不释放的习惯。面试官如果追问“这段代码在长时间运行的服务里内存怎么管理”，你不能只说“LeetCode 不管这个”。至少要能说出结果链表由调用方负责释放，或者用节点池分配来减少碎片。

4.4 常见问题速查表

我把这题最常见的几个问题和对应解决办法整理成一张表，方便你复习时快速对照：

这张表基本覆盖了我见过的绝大部分新手错误，也包括我自己早期反复踩过的那些。

5. 从这题延伸出去：模板化思考与类似问题

5.1 进位模拟题的通用模板：三个循环变量 + 两个数组/链表

做完这道题你会发现，它的套路可以抽象成一套“进位模拟通用模板”。核心思想是同时遍历两个数据源，加上来自前一位的进位，计算当前位结果和新的进位，直到两个数据源都耗尽且进位为 0。

这个模板用伪代码表达就是：

i = j = 0; carry = 0; while (i < len1 || j < len2 || carry) { sum = carry; if (i < len1) sum += a[i++]; if (j < len2) sum += b[j++]; result[current++] = sum % 10; carry = sum / 10; }

如果你把这个模板套到数组求和、字符串数字求和、二进制数求和上，会发现核心逻辑惊人地一致。区别只在于：

• 进位的基底不同，十进制是 10，二进制是 2。
• 数据的存储方式不同，可能是链表、数组或者字符串。
• 数据的指向不同，链表是节点指针后移，数组是下标递增。

一旦你意识到它们都共享“sum + carry”和“% base / base”这两个动作，刷这类题的速度会明显提升，因为你不需要再从头思考，只需要做局部改写。

5.2 变体场景：字符串相加、二进制相加、链表合并

字符串相加是一个非常经典的变体。比如给两个字符串形式的数字，让你返回它们的和，同样用字符串表示。此时你不能用标准库的大整数转换，解决方式就是把字符串从右往左遍历，维护进位。注意字符要先减成对应的数字，计算完当前位置后还要反向拼接结果。

二进制相加也是同一个套路，只是取模和整除的基底从 10 变成 2。例如 [1,1] 和 [1]，二进制 1+1=10，结果还是 0?1? 不对，应该是 [1,0]，对应十进制的 2。这个问题在嵌入式、位运算相关面试中经常出现，模板完全一致。

还有一种变体是链表合并，虽然它没有进位逻辑，但它和这题在“同时遍历两个链表、循环条件用或、处理剩余长度”这些结构上非常相似。所以 LeetCode 把“合并两个有序链表”和“两数相加”放在同一类链表训练里不是偶然，它们的核心都是游标加判空。

如果你想把模板吃透，我建议在你刷完这题后，马上挑两道字符串相加和二进制相加类的题做练习。我试过这个训练路线，比继续盲目刷更多图形题有效得多，因为你在反复使用同一套抽象。

5.3 个人建议：刷题时如何把“会做”变成“熟练”

最后一个部分，说说怎么把“看懂了”变成“自己写得又快又稳”。

我第一次做这道题时，看题解秒懂，但合上电脑自己写，还是会把 head 和 cur 搞混。后来我给自己定了一个规矩：每道链表题都先写一个 createNode 辅助函数，每次都强制使用虚拟头节点，哪怕题目不需要也先按这个结构搭好。这个规矩看起来很笨，但当你把“链表题先搭骨架”变成肌肉记忆后，真正困难的逻辑部分才能专注思考。

还有一点是调试技巧：遇到链表类的错误，不要只靠代码瞪眼，用打印函数把每一步的指针走向输出出来。写一个 printList 函数，在每个循环迭代后都打印当前节点值和 next 指针的指向，很快就能发现是哪一步把链表搞断了。这个技巧对实际工作里的嵌入式或者底层开发也有帮助，你不能强行假设一个复杂的数据结构永远不出错。

另外我建议你把这题的三种解法都试一遍。先用最容易理解的虚拟头节点法，然后试着不用虚拟头节点单独处理第一个节点，最后再尝试用递归写一版。三种写法的对比能让你明白同一个逻辑在不同表达方式下的差别，也能帮你理解为什么工程上更推荐虚拟头节点。多写几版之后，如果再遇到类似的题，你脑子里会出现好几种方案，而不是背唯一解。

最后分享一个我自己习惯的小技巧：在提交前，先在心里默念三个检查点。第一个是循环条件是 or 不是 and，第二个是返回的是头节点不是尾节点，第三个是最高位有没有补上 final carry。这三句话看着简单，却能拦住绝大多数错误。LeetCode 2 的代码量并不大，真正拉开差距的就是这些细节。希望你把这道题吃透之后，再去面对各种链表和进位题时，能有一种底气和从容。