很多人第一次刷题时都绕不开 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。节点挂载的顺序是malloc 一个新节点给 val 和 next 赋值让当前尾节点的 next 指向新节点把 tail 更新成新节点。这里的 tail 就是一条“始终跟随最后节点”的指针它记录的是结果链表的尾部。如果没有 tail每次挂节点都得从头遍历到尾部时间复杂度直接变成 O(n^2)显然不能接受。3.3 测试用例验证从普通到刁钻本地跑代码时我建议至少覆盖下面这几个用例用例链表 A链表 B期望结果考察点1000空加法、全零22-4-35-6-47-0-8基本进位39-9-910-0-0-1连续进位 最高位进位41-23-4-54-6-5长度不等591-90-0-1短链表进位传递到长链表以用例 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表示 213-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 刷题就把这一题当成一面镜子多跑几个用例卡住了再回头看循环条件收获会非常明显。