企业官网建设流程全解析

很多人第一次刷题时，都绕不开 LeetCode 第 2 题《两数相加》。这道题表面上是“链表 + 进位模拟”，实际上考的是你对指针操作、边界处理、内存分配的理解深度。我见过不少人能在纸上画出思路，但一到 C 语言就卡在 malloc 和空指针上。这篇文章把这道题从头到尾掰开揉碎，包括完整可运行的代码、每一步为什么这样写，以及实际调试中容易踩的坑。适合刚学链表的人，也适合准备面试想快速复习经典题的开发者。

1. 题目解读与破题思路：这道题到底在考什么

1.1 逆序链表存储的前因后果

题目给出的两个数字是用链表表示的，而且每个节点只存一位数字，数字的 low 位在链表的最前面。比如数字 342，链表就是2 -> 4 -> 3；数字 465，链表就是5 -> 6 -> 4。很多初学者第一眼看到逆序会不习惯，心想为什么不能顺着存，那样不是更符合我们读数字的习惯吗？

这里面其实有一个很实际的考虑：加法计算时，我们一定是先算个位，再算十位、百位，也就是从低位往高位算。如果链表按照正常顺序存储，个位在链表尾部，那每次做加法都得先从头跑到尾，做完一次加法还要往回走，算法会变得很别扭。就算用递归，最终也要先找到尾部，过程绕一圈。而逆序存储等于把个位放在头节点，我们直接从头往后遍历，正好匹配竖式加法的计算顺序。理解了这一点，这道题的核心思路就已经抓住了一半。

另外，这种逆序存储的方式并不是 LeetCode 独创的。很多编程语言里实现大数运算时，为了便于进位和逐位操作，也会把低位放在数组或链表的开头。可以说，这道题是用了一个贴近真实计算模型的抽象，而不是为了为难人故意倒着存。

1.2 竖式加法在链表上的完整投影

现在把两个链表想象成两串数字，我们要做的就是用两个指针分别从头开始走。每走一步，把两个指针对应的节点值相加，再加上上一位产生的进位，结果如果超过 9，就把超过部分留给下一位。

稍微抽象一下，就是维护一个整型变量 carry，初始值为 0。每轮循环，计算total = l1->val + l2->val + carry，当前位的结果节点值就是total % 10，下一位的进位就是total / 10。两个链表指针各自向后移动一步，直到两个链表都遍历完，并且 carry 也变成 0，循环结束。

这个逻辑看起来简单，但里面藏着三个容易出错的地方。第一，两个链表可能不一样长，短链表走到尾之后，再取值要当 0 处理，不能直接访问空指针。第二，最高位相加可能产生新的进位，比如 999 + 1，最后会多出一位 1，这个节点必须在循环里被创建出来。第三，C 语言里 malloc 出来的节点必须手动初始化 next 指针，否则后面 tail 指向它时，再设置 next 会出问题。

时间复杂度方面，因为只需要分别遍历两个链表各一次，所以是O(max(m, n))，m 和 n 分别是两个链表的长度。空间复杂度在迭代法里主要取决于结果链表的长度，也是O(max(m, n))。注意这里结果链表理论上最多比最长的输入链表多一位，比如 999 + 1 得到四位数，所以空间复杂度写成O(max(m, n))是安全的。

2. 核心细节解析：C 语言实现里的关键节点

2.1 链表节点定义与 malloc 的正确姿势

在 LeetCode 环境里，结构体是提前定义好的，通常是：

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

自己写代码的时候，我习惯用typedef struct ListNode ListNode;把类型名简化一下，减少后续struct关键字带来的视觉噪音。不过要注意，LeetCode 的编译环境里已经定义过struct ListNode，你自己练习时不用重复定义，否则会冲突。

创建新节点时，标准写法是：

ListNode *node = (ListNode *)malloc(sizeof(ListNode)); if (node == NULL) { // 处理分配失败 } node->val = sum % 10; node->next = NULL; tail->next = node; tail = node;

这里有两个非常容易忽略的细节。第一个是 malloc 之后一定要检查返回值。在线判题一般情况下不会内存耗尽，所以你只写node->val = ...也能通过测试，但工程化一点的代码我会习惯性加空指针检查，防止在真实项目里翻车。第二个是要记得把node->next手动置为 NULL。malloc 出来的内存内容是随机的，不是自动清零的。如果不置 NULL，最后遍历结果链表时可能会多走出很远，甚至在 LeetCode 上出现奇怪的报错。

2.2 虚拟头节点到底省了什么事

很多链表题里都有一个经典技巧：设置一个虚拟头节点，让它的 next 指向真正的头节点。这样做的最大好处，是避免在循环外面单独判断“当前是不是第一个节点”。

想象一下，如果不设置虚拟头节点，你可能会写出这样的代码：

ListNode *head = NULL; ListNode *tail = NULL; // 第一次创建节点时要让 head = node，后续要让 tail->next = node

每次循环都得判断head == NULL，代码分支变多，而且容易在连续赋值时漏掉 tail 的更新。更麻烦的是，如果两个链表都是空链表，你还需要特殊处理返回 NULL 的情况。

有了虚拟头节点，代码就变成了一种状态驱动的写法：

• 新节点永远挂在tail->next上；
• tail永远指向当前最后一个节点；
• 循环结束后直接返回dummy.next。

在这个实现里，我用的虚拟头节点是栈上变量，也就是struct ListNode dummy;。注意我返回的是dummy.next，而不是&dummy。这个区分很重要。dummy.next指向的是堆上第一个真实的节点，生命周期是安全的；而dummy本身是局部变量，函数返回后就失效了，绝不能返回它的地址。

2.3 循环条件的取舍：到底是 && 还是 ||

我第一次写这道题时，循环条件用的是while (l1 != NULL && l2 != NULL)，结果逻辑只处理了两个链表等长的情况，后面一旦出现长度差或者最后还有进位，代码就崩了。后来才改成正确的写法：

while (l1 != NULL || l2 != NULL || carry > 0)

这个条件非常优雅地覆盖了所有情况：

• 两个链表都没走完时进入循环，是正常加法；
• 一个走完、另一个没走完时，把走完的一边视为 0；
• 两个都走完了，但 carry 还有值时，说明最高位多出了一个 1，必须再创建一个节点。

有些同学可能会问：为什么要把carry > 0也放在循环条件里，而不是在循环结束后单独补一个if (carry > 0)？你也可以那样做，代码会更显式，但放在循环条件里可以让逻辑更统一，少一个分支。两种写法都对，关键是不能漏掉这个进位。

3. 实操过程与代码落地：一步一步把它写出来

3.1 完整可运行的 C 语言迭代解法

下面是我个人比较喜欢的一个写法，简洁、清晰，同时把边界情况都处理干净：

#include <stdio.h> #include <stdlib.h> struct ListNode { int val; struct ListNode *next; }; struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { struct ListNode dummy; dummy.next = NULL; struct 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; carry = sum / 10; struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode)); node->val = sum % 10; node->next = NULL; tail->next = node; tail = node; if (l1 != NULL) { l1 = l1->next; } if (l2 != NULL) { l2 = l2->next; } } return dummy.next; }

如果你在做完整工程，还需要写一个辅助函数把数组转换成链表，再写一个函数打印链表，这样才能在本地完整跑起来。LeetCode 上只需要交上面这个函数即可。

这里还有一个性能上的小细节：l1->next是在循环末尾统一移动，所以即使一个链表已经为空，另一个链表继续走时，空的那边不会执行l1 = l1->next，这样就不会出现空指针访问。

3.2 每一行代码背后的逻辑拆解

先看dummy的初始化。dummy.next = NULL一定要写。链表题的初始化，最怕的就是“有默认值”的错觉。栈变量 dummy 的 next 字段如果不置空，后面 tail 第一次挂节点时，dummy.next 指向哪里都不知道，最终返回的值就不可控了。

然后是v1和v2的取值。这里用三元运算符做空指针判断，是这道题的灵魂之一。很多同学会先判断l1 != NULL再写两个分支，但三元表达式让代码更紧凑。它的含义很清楚：如果一个链表已经走到尽头，这位的数字就是 0。比如 999 + 1，循环第一次计算的是 9 + 1 + 0，第二次、第三次，l2 已经为空，就按 0 处理，算的是 9 + 0 + 0。

sum / 10是当前位的进位值，sum % 10是当前位的结果值。因为两个一位数相加，再加上最多一个进位，最大是 9 + 9 + 1 = 19，所以carry只能是 0 或 1。这也是十进制加法的一个天然约束。如果你把进制改成 2 或其他进制，这个假设就不再成立，计算逻辑需要调整成sum % base和sum / base。

节点挂载的顺序是：

1. malloc 一个新节点；
2. 给 val 和 next 赋值；
3. 让当前尾节点的 next 指向新节点；
4. 把 tail 更新成新节点。

这里的 tail 就是一条“始终跟随最后节点”的指针，它记录的是结果链表的尾部。如果没有 tail，每次挂节点都得从头遍历到尾部，时间复杂度直接变成 O(n^2)，显然不能接受。

3.3 测试用例验证：从普通到刁钻

本地跑代码时，我建议至少覆盖下面这几个用例：

以用例 3 为例，999 + 1 = 1000，逆序表示就是0->0->0->1。如果你在写代码时把carry > 0漏掉了，第三个 0 之后循环就停了，少了最后一个 1，整个结果直接对不上。这个用例几乎是我每次验证这道题时的必测项。

4. 常见问题与排查技巧实录

4.1 一写就错：while 条件用了 && 导致结果丢失

我见过最多的一种错误，是把循环条件写成while (l1 != NULL && l2 != NULL)。这样一旦某个链表先走完，循环立刻结束，剩下的所有节点和进位全部被丢弃。比如1->2和3->4->5相加，结果是 432 + 5? 不，1->2表示 21，3->4->5表示 543，和应该是 564，顺序是4->6->5。用&&的条件，只会得到4->6，中间少了最高位 5。

排查这种问题有一个很蠢但有效的方法：在循环里加上打印语句，打印每一轮的 l1 当前值、l2 当前值、carry 和 sum。只要打印一轮，你立刻就能发现循环提前退出的位置。线上判题时不能加打印，但本地调试完全可以用临时打印，定位完再删掉。

4.2 空指针崩溃：取链表节点的值时没判空

循环条件里用||连接三个条件后，循环内部很容易出现这种情况：

while (l1 != NULL || l2 != NULL || carry > 0) { int sum = l1->val + l2->val + carry; // 危险写法 }

当其中一个链表已经为空时，l1->val就是空指针访问，程序直接崩溃。这种错误在本地几乎必现，因为只要两个链表长度不同，就会触发空指针。解决办法就是前面代码里展示过的：先用三元表达式取出v1和v2，空链表对应的值为 0，然后再计算。

这里我想多讲一句：访问指针前先问自己“这个指针此时一定不为空吗”，是 C 语言链表调试里最重要的思考习惯。很多莫名的段错误，源头都是这里。

4.3 返回地址指向栈变量：典型悬空指针

另一种头疼的错误是把虚拟头节点直接返回：

return &dummy;

这相当于把一个栈变量的地址暴露给了调用者。函数返回后，栈空间被回收，这个地址指向的内容随时可能被其他代码覆盖，结果链表看起来像“有值”但又“不知道什么时候会变”。真正的正确做法是返回dummy.next，因为dummy.next指向的是 malloc 出来的堆内存，生命周期不会因为函数结束而消失。

如果你确实喜欢用malloc创建虚拟头节点，那返回head->next后，还需要手工free(head)释放虚拟头节点，否则会造成一点小内存泄漏。虽然判题平台不关心，但写多了 C 代码就会养成 free 的习惯。

4.4 递归解法：简洁但要注意栈开销

这道题也可以写成递归。核心思路是把“当前节点的加法结果”交给下一层递归去处理。因为 C 语言每次函数调用都会分配栈帧，所以递归深度等于链表长度。如果链表非常长，比如几万个节点，递归可能爆栈。

下面是一个参考实现：

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { return addTwoNumbersWithCarry(l1, l2, 0); } struct ListNode* addTwoNumbersWithCarry(struct ListNode* l1, struct ListNode* l2, int carry) { if (l1 == NULL && l2 == NULL && carry == 0) { return NULL; } int v1 = (l1 != NULL) ? l1->val : 0; int v2 = (l2 != NULL) ? l2->val : 0; int sum = v1 + v2 + carry; struct ListNode *nextNode = addTwoNumbersWithCarry( (l1 != NULL) ? l1->next : NULL, (l2 != NULL) ? l2->next : NULL, sum / 10 ); struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode)); if (node == NULL) { return NULL; } node->val = sum % 10; node->next = nextNode; return node; }

递归代码看着很简洁，但有一个实际问题：它先递归到最深层，再一层层往回创建节点，所以最终链表是从高位开始构建的。这个思路对理解“先算低位、后构建高位”有帮助，但在 C 语言里，我的建议还是优先用迭代法。尤其是面试时，迭代法更容易讲清楚时间和空间复杂度，也更容易现场改 bug。

4.5 不要犯“ l1++ ” 这种数组思维错误

链表不是数组，节点在内存中不是连续排列的，所以绝对不能用l1++来移动指针。链表里每个节点保存的是 next 指针，你只能通过l1 = l1->next跳到下一个节点。这个错误在新手身上非常常见，因为它把链表指针当成了数组指针。一旦写了l1++，程序不会编译报错，但运行时指针会跳到莫名其妙的内存区域，轻则输出乱码，重则段错误。排查到这种问题，先看自己是不是又把链表当数组了。

5. 从这道题延伸出去：链表和进位模拟还能怎么玩

5.1 如果链表是正序存储，该怎么办

很多扩展题里，链表不是逆序的，而是按高位到低位存储，比如3->4->2就表示 342。这时候直接模拟竖式加法会遇到对齐问题：两个数长度不同，低位在哪根本不知道，总不能从尾巴往前遍历。

常见的解法有两个。第一个是先把两个链表反转，用我们上面讲过的逆序加法算完，再把结果反转回来。第二个是用两个栈分别保存两个链表的值，弹出的时候从低位开始相加，生成的新节点用头插法挂到结果链表的前面。两种方法的道理其实一样：化正序为逆序，本质都是先拿到低位再模拟进位。

如果你在面试里遇到这个变体，不妨先写反转法，因为它代码逻辑最接近原题，不容易出错。时间复杂度是 O(max(m, n))，空间复杂度也是 O(max(m, n))。面试官如果再追问“能不能不用额外空间”，你还可以说在允许修改原链表的情况下，先反转输入链表，算完再反转回来，额外空间可以做到 O(1)。

5.2 换一个 base，就是通用的大数加法

这道题看起来是在写链表，实际上是在实现“任意精度整数加法的核心逻辑”。把十进制换成二进制、八进制、十六进制，甚至一百万进制，逻辑都完全一样，只要把取模的基数从 10 改成对应进制即可。

有些语言里大整数运算就是这样实现的：用一个数组或链表保存每一位数字，加法时从低位开始，维护 carry，逐位计算。对于一个不能直接用 int64 存储的超大整数来说，进位模拟是唯一可靠的手段。理解了 LeetCode 第 2 题，再去看很多大数运算库的源码，你会发现里面到处是这个套路。

同样地，乘法也可以从这个思路延伸。大数乘法通常是竖式乘法的扩展：每一位相乘、叠加、进位。如果你把加法的题彻底吃透，后面遇到“字符串相乘”“链表相加”这类题时，至少不会一头雾水。

5.3 一题多解的价值：为什么我建议你复写三遍

这道题我前前后后写过很多遍，每次用不同方式写，体会都不一样。第一遍直接照题解写迭代法，理解流程；第二遍闭眼默写，刻意卡在边界条件上；第三遍尝试递归解法，去感受函数调用栈和指针传递的差异。你会发现，同一道题，写三遍之后，你真正记住的不再是答案，而是思考方式。

面试时遇到原题，很多人会兴奋地开始写，结果一紧张就把carry > 0漏掉。如果你在平时练习时已经把各种边界条件都跑过，甚至亲手踩过坑，面试时就是肌肉记忆，根本不用靠临场推演。这也是为什么我一直建议大家刷题不要贪多，经典题反复做，远比每题只做一遍要有效。

最后说点我自己的体会。这道题我最初用其他语言写，觉得十分钟就搞定了；后来用 C 语言重写，被一个空指针卡了大半个小时。原因是我在循环里没有判断l1是否为 NULL 就直接取l1->val。从那以后我给自己定了个规矩：只要涉及链表和树，访问成员之前先问自己一句——这个指针现在一定不为空吗？这道题看似基础，但能把边界条件、内存分配、指针移动全部串起来。如果你也刚开始用 C 刷题，就把这一题当成一面镜子，多跑几个用例，卡住了再回头看循环条件，收获会非常明显。