如果你正在准备 C 相关的面试或者刚开始刷 LeetCode那道经典的“2. 两数相加 c”我建议你别跳过。题目本身不复杂给你两个用链表表示的非负整数数字的每一位按逆序存储在一个节点里你要把两个数加起来然后用同样的链表形式返回结果。就这么简单但简单背后藏着不少 C 工程向的考点比如指针操作、内存管理、边界条件处理、递归和迭代两种思维切换甚至还有“如果数字大到溢出该怎么办”这类送命题。这道题适合谁来读两类人。第一类是刚学完 C 语法、想通过算法题巩固链表和指针的人第二类是准备面试、想把这题答出层次感的人。无论是哪种你都能从这篇拆解里拿到可以直接抄作业的代码、测试用例、以及书本上不会写的实战经验。1. 题目到底在说什么链表表示数字的巧妙之处1.1 数字链表的还原与误解先给不熟悉链表的读者补个背景。所谓链表节点在 C 里是一个结构体struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };题目说“数字按逆序存储”这句话是整道题的命门。比如数字 342在链表里是 2 - 4 - 3而不是 3 - 4 - 2。为什么要逆序很多人第一反应是“故意给我制造麻烦”其实恰恰相反逆序存储让低位对齐变得极其自然。你做加法时从个位开始加链表头正好就是个位一路往后走就是十位、百位、千位完美配合小学就学过的竖式加法。如果题目把数字正序存储反而需要先反转链表或者借助栈那才是真的恶心人。我用一个例子说明数字 807 在链表里长这样7 - 0 - 8。它表达的是一个三位数但和数组下标不一样链表的第 0 个节点并不代表“最高位”而是“个位”。所以读完题目之后不要想着“把链表转成整数算完再转回链表”。这个思路在大整数场景下根本行不通后面我会专门说为什么。1.2 约束条件里藏着的信息题目给的条件通常有这么几条两个链表都是非空的每个节点存储一位数字范围是 0-9除了数字 0 本身整个数字不会以 0 开头。“非空”意味着你不需要处理空链表输入可以直接假设 l1 和 l2 至少有一个节点。“不会以 0 开头”是说不会出现 0 - 3 - 2 这种代表 230、但实际上首位是 0 的情况。唯一例外是数字 0 本身它会以单节点 0 - nullptr 的形式出现。这些约束不是废话它们决定了你不需要在代码里做额外的合法性校验。有很多初学者在边界条件上过度设计反而把简单题写复杂。我见过有人在函数开头写了一大段“如果 l1 为空则直接返回 l2如果 l2 为空则直接返回 l1”的逻辑这没有错但因为题目保证非空这段分支在 LeetCode 的评测里根本不会触发。当然留着也不是不行作为一个健壮性考虑但你要知道主路径是哪条。1.3 这道题想考察的三种能力放到面试场景里面试官出这道题通常不是想让你证明自己会写链表而是要同时看三件事你能不能把现实问题两数相加抽象成数据结构上的运算链表遍历 进位传递你能不能处理“两个输入长度不一致”和“最后一位还有进位”这两个边界情况你能不能写出简洁、不容易出内存问题的 C 代码并说清楚时间和空间复杂度。所以我的建议是不要一上来就背模板先把“竖式加法”这个模型在纸上画一遍再用代码还原。这也是我接下来要展开的核心思路。2. 核心思路小学数学加法立竖式模拟2.1 竖式加法的计算模型想想你在小学做 342 465 时的步骤先加个位2 5 7没有进位再加十位4 6 10写 0 进 1再加百位3 4 1进位 8写 8结果是 807。在链表里这个过程完全一致。你只需要维护一个变量 carry它的取值只能是 0 或 1因为两个一位数相加最大是 9 9 1 19进位不可能超过 1。每一轮循环把 l1 的当前节点值、l2 的当前节点值、以及上一次的进位 carry 加到一起得到 sum然后新节点值 sum % 10新进位 sum / 10。这个模型就是整道题的核心。只要 carry 在某一轮循环之后还是 1说明最高位还有进位需要额外再创建一个节点值为 1。这是新手最容易漏掉的地方后面我会重点提醒。2.2 为什么用虚拟头结点dummy node在实现链表类题目时有一个非常经典的技巧创建一个虚拟头结点 dummy然后让一个游标指针 cur 从 dummy 开始串新链表。最后返回 dummy-next。为什么不直接创建一个真实的头结点然后返回它因为头结点在什么时候创建、由谁来“指向”它是个容易出错的细节。如果直接用 ListNode* head nullptr然后循环里判断 head 是否为空代码会多出很多分支而且很容易把指针关系写乱。虚拟头结点的思路是反正我要从头到尾串一串新节点那就先放一个不参与业务的“占位节点”在最前面让所有新节点都统一用cur-next new ListNode(...)这种方式接到后面完全不用区分首节点和后续节点。循环结束虚拟头结点的 next 就是真正的结果头结点。这个模式在链表题里几乎是无敌的它把“第一个元素特殊化”全部抹平代码结构更统一出错率更低。很多人会纠结 dummy 节点的内存泄漏问题。在 LeetCode 的评测环境里你 new 出来但没 delete 的内存一般不会影响判题正确性但在真实工程里裸指针 new 还是要配套 delete。这道题的结果链表本身就是需要返回的所以返回部分不需要你手动释放而 dummy 节点是临时辅助严格来说应该释放。只是在面试白板或在线评测中大家通常不会特意去 delete 这个 dummy我建议你心里清楚这一点如果你写的是完整工程代码可以在返回之前对 dummy 做一次 delete。2.3 复杂度分析时间与空间时间复杂度很好判断只需要同时遍历两条链表直到较长的链表走完且进位也处理完毕。假设 l1 的长度是 ml2 的长度是 n因为每位节点最多访问一次最坏情况下循环次数是 max(m, n) 1多出来的 1 来自最后可能的进位。所以时间复杂度是 O(max(m, n))。空间复杂度要分两种情况说。如果你创建了一条全新的链表来存结果最常见做法额外空间主要是结果链表本身长度产生的长度最多是 max(m, n) 1所以空间复杂度也是 O(max(m, n))。如果你选择在 l1 或 l2 的原链表上做修改原地更新那额外空间可以是 O(1)只是修改过程会破坏输入链表面试时需要在注释或口头上说清楚。LeetCode 默认允许修改输入链表吗这个问题不好一概而论但很多答案是“可以修改”因为题目没有明确禁止。面试时候最好先问一句。3. 完整代码实现与逐行拆解3.1 迭代解法的标准模板先把 C 的迭代解法完整贴出来这是我认为最好理解、也最适合作为考场默写版本class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dummy new ListNode(0); ListNode* cur dummy; int carry 0; 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 new ListNode(sum % 10); cur cur-next; carry sum / 10; } return dummy-next; } };这段代码之所以推荐是因为 while 循环的条件是l1 || l2 || carry把“两个链表都走完但还有进位”的场景直接包含进去了。如果写成while (l1 || l2)那当 l1 和 l2 都为空、但 carry 还是 1 的时候循环会提前退出最高位的 1 就丢了。等会我专门用一个测试用例演示这个坑。3.2 关键代码行的含义与边界处理int sum carry;先把上一轮的进位加到本轮总和里。这一行必须放在最前而不是在判断 l1、l2 之后再单独处理进位。if (l1) { sum l1-val; l1 l1-next; }如果 l1 还有节点就取值并后移没有就直接跳过。这样两条链表长度不一致时短的那条走完后后面的循环依然能正常执行。cur-next new ListNode(sum % 10);把本轮计算出的个位数字挂到新链表尾部。carry sum / 10;整数除法的结果天然就只会是 0 或 1因为 sum 最大是 9 9 1 19。这里不需要再对 carry 做取模直接用除法就行。最后return dummy-next;绕开虚拟头结点返回真正的链表头。这段代码有三个隐藏细节值得注意新节点创建用的是new ListNode(sum % 10)构造函数会把 next 自动置空不需要手动置空。指针 l1 和 l2 在循环中被修改所以函数结束后外部的原始链表指针也会被影响。在 LeetCode 中这通常不构成问题因为单次调用结束就结束了。但如果你写一个工具函数多次调用 addTwoNumbers 时用的还是原始链表指针那就要注意第一次调用之后这些指针已经走到链表尾部了。我的习惯是在函数内部再用两个局部指针 p1 l1, p2 l2 去遍历这样不破坏入参指针。代码多两行但更保险。sum % 10 和 sum / 10 的关系一个是取个位一个是取进位。因为 sum 最大是 19carry 只会是 0 或 1sum 最小是 0不会出现负数。3.3 递归解法换个角度写更短代码这道题也可以用递归写核心思路一样处理当前位递归处理后续节点最后把进位一层层带出来。class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry 0) { if (!l1 !l2 carry 0) { return nullptr; } int val carry; if (l1) val l1-val; if (l2) val l2-val; ListNode* node new ListNode(val % 10); node-next addTwoNumbers( l1 ? l1-next : nullptr, l2 ? l2-next : nullptr, val / 10 ); return node; } };递归版本的优点是逻辑表达很接近数学归纳法先算当前位再用同样方法处理剩余链表终止条件是“两条链表都空了并且进位也没了”。缺点是递归深度等于链表长度如果链表很长比如几万节点会出现栈溢出风险。LeetCode 的测试数据里链表长度一般不会达到几万所以递归可以过。但面试时如果被追问“能不能写出迭代版”你最好两个版本都能给出来同时说明各自的适用场景。4. C 实现中的四大坑与优化技巧4.1 内存管理new 出来的节点谁来释放C 不像 Java有虚拟机自动回收内存。你在循环里每 new 一个 ListNode都会在堆上分配一块内存。LeetCode 评测时判题器会在用例跑完后统一回收所以单看程序本身不会有问题。但这不意味着你可以完全无视内存问题。在真实工程里如果这个函数被频繁调用且结果链表用完没人释放就会造成内存泄漏。我个人建议在本地练习时写一个辅助函数 deleteList用来释放整条链表void deleteList(ListNode* head) { while (head) { ListNode* next head-next; delete head; head next; } }同时虚拟头结点 dummy 在返回之前可以 delete 一下。不过要注意delete dummy 必须在返回 dummy-next 之前并且不能误删结果链表。像这样ListNode* result dummy-next; delete dummy; return result;很多教程不写这一行不写不代表正确只是评测环境替你兜底了。你想实现一个更完整的函数就把这个释放逻辑加上。4.2 指针移动与空指针判定的顺序初学者容易犯一个错误先移动指针再判定是否为空。比如// 错误示范 while (l1 || l2) { sum l1-val l2-val carry; // l1 或 l2 可能已是 nullptr l1 l1-next; // l1 为 nullptr 会崩溃 l2 l2-next; }这就是典型的“没判空就取值”。正确做法是在取值之前判空取值之后才移动指针。上面标准模板里的写法是先判空再取值再移动顺序是安全的。另外还有一个隐蔽的坑l1 ? l1-next : nullptr这种三目表达式你写的时候要注意括好否则和后面的参数传参会混在一起。我测试过 GCC 和 Clang一般不会报错但可读性差建议加括号。4.3 不同长度链表与最后一位进位的处理这是最常出问题的地方。比如l1 [9, 9, 9]l2 [1]手动模拟9 1 10当前位 0进位 1第二位9 0 1 10当前位 0进位 1第三位9 0 1 10当前位 0进位 1最后还有一位进位 1所以结果是 [0, 0, 0, 1]。也就是 999 1 1000。如果用while (l1 || l2)作为循环条件走到第三位结束后l1 和 l2 都空了carry 1 还在手里循环却已经退出结果变成了 [0, 0, 0]少了一个最高位 1直接 Wrong Answer。这就是为什么我强烈建议循环条件写成l1 || l2 || carry把最后一个进位也纳入循环处理。同理递归版本的终止条件也必须把 carry 0 考虑进去否则最后一位进位会丢失。4.4 空间优化尝试在 l1 上原地修改如果你不想额外创建一整条新链表可以选 l1 作为结果链表在遍历过程中直接修改 l1 节点的值只在链表长度不够时再补齐新节点。这样能省掉结果链表本身带来的额外空间把额外空间压到 O(1)。大致思路先正常遍历 l1 和 l2累计进位更新 l1 当前节点值为 sum % 10如果 l2 更长就继续在 l1 链表上追加新节点遍历结束后如果 carry 为 1在尾部追加值为 1 的新节点。这个方案写起来比“新建链表”要繁琐一些而且会破坏输入数据所以 LeetCode 默认场景下我不推荐作为首选。但在面试里面试官问你“能不能优化空间”时你能说出这个思路会是一个加分项。注意优化空间的前提是不能改变函数对外返回的结果语义只是把新建节点换成修改原节点。4.5 关于大整数溢出为什么不能先转 int这是我特别想强调的一个认知误区。有人一看题目说“两个数字相加”第一反应是先把链表转成整数比如把 [2,4,3] 转成 342加完再转回链表。这个方案在数字很小的时候能过但 LeetCode 的测试用例里链表长度通常可以到 100 位甚至更多。int 最多表示大约 21 亿long long 也就 19 位十进制数完全装不下 100 位的大整数。而且题目本身要考察的就是手动模拟竖式加法而不是利用语言原生的整数加法。一旦你把链表转成整数思路就跑偏了面试官大概率会追问“如果链表有 1000 位怎么办”。所以老老实实逐位相加是最好的也是唯一能通吃大数场景的方案。5. 测试用例、边界条件与面试追问5.1 必测的 5 类用例写算法题最怕的是“代码看着对了但测试没覆盖到”。这道题我建议你准备以下五类测试用例用例类型输入期望输出说明普通情况[2,4,3] [5,6,4][7,0,8]342 465 807两个零相加[0] [0][0]0 0 0最后一位有进位[9,9,9] [1][0,0,0,1]999 1 1000最容易漏的用例长度不一致[1,8] [0][1,8]81 0 81中间过程连续进位[1,9,9] [9][0,0,1]991 9 1000手动调试时可以写一个简单的链表打印函数void printList(ListNode* head) { while (head) { cout head-val; if (head-next) cout - ; head head-next; } cout endl; }配合 LeetCode 的本地测试用例基本能覆盖百分之九十的错误。5.2 面试官可能会追问的四个变体面试官在你解完之后很少会让你直接离场通常会变着法子追问。我把常见的追问方向整理成下面几个如果链表节点存放的不是一位数字而是一个 int怎么处理答案核心是进位不再是 0 或 1而是 sum / 10可能大于 1。流程不变只是 carry 可能变成更大的数仍然用 while 循环处理。如果数字正序存储怎么办思路是先把两条链表反转或者用栈把节点压进去再做同款加法最后把结果反转回来。复杂度仍然是 O(max(m, n))但代码量会增加一些。如果输入是单向链表内存有限如何考虑空间占用可以引出“原地修改”的思路复用 l1 节点减少新节点分配只在需要时才追加。如果链表尾部出现循环环这题还能做吗这是链表进阶题需要先判环。不过 LeetCode 原题没有环面试中如果被追问可以识别出这是“带环链表检测 两数相加”的综合题思路是先找环入口、断开环或者标记终点再正常相加。不建议把答案背得很死板面试官更希望听到你“分析问题的思考过程”。你可以说先确认输入是否有环如果有环加法就变成无限循环了得先解决环的问题。5.3 本地调试与 C 环境准备很多读者可能刚入门 C还没在本地搭环境。我以 VSCode 为例简单说下调试链表题目的环境准备思路装好 C/C 扩展配置好编译器Windows 上可以是 MinGW-w64 或 MSVCmacOS 上可以用 clangLinux 上可以用 g然后新建一个 .cpp 文件把 ListNode 结构体、addTwoNumbers 函数、main 函数和一个打印辅助函数写在一起。在 main 里手工构造两个链表调用函数再把 printList 结果打到控制台观察输出是否符合预期。#include iostream using namespace std; struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; // 把 addTwoNumbers 的实现复制到这里 // 辅助函数根据 initializer_list 构造链表 ListNode* buildList(initializer_listint vals) { ListNode* dummy new ListNode(0); ListNode* cur dummy; for (int v : vals) { cur-next new ListNode(v); cur cur-next; } return dummy-next; } int main() { ListNode* l1 buildList({2, 4, 3}); ListNode* l2 buildList({5, 6, 4}); Solution s; ListNode* result s.addTwoNumbers(l1, l2); printList(result); deleteList(result); deleteList(l1); deleteList(l2); return 0; }这样你在本地就能单步看每一轮循环中 l1、l2、carry 的变化比纯靠脑子里跑流程要直观得多。我强烈建议新手学会用调试器打断点而不是全靠 cout 打印。打断点能让你看到每一行执行后各个变量的值对理解指针之间的指向关系帮助巨大。5.4 如何从这道题延伸学习 C如果你已经刷完这一题别急着去做下一道。这道题其实牵出了很多 C 的知识点动态内存分配 new/delete、结构体指针、构造函数重载、作用域和生命周期、三目运算符、引用与值传递等等。你可以顺手把这些知识点串起来复习一遍。尤其是“指针作为函数参数”这一点。addTwoNumbers 接受两个 ListNode*在函数内部修改 l1、l2 指针本身不会影响外部传入的指针变量因为参数传递是值传递指针变量本身被拷贝了一份。但修改 l1-val 或者 l1-next 会影响外部链表的节点内容因为两个指针指向同一个内存地址。这个区别我刚学 C 时经常搞混建议你一定要动手验证一下。另外刷这道题的时候可以把 C 版本的 ListNode 定义和 Java / Python 的版本做个对比你会理解为什么 C 需要手动管理内存而 Java 里到处传引用Python 里更省心。横向对比能加深记忆也有助于在和别人讨论算法时快速切换语言还能顺便在简历里写上一句“熟悉 C 内存管理与常见数据结构操作”这可比空喊口号有说服力多了。最后再分享一个我自己的小习惯刷链表题时先在纸上画一个简单的链表画两个节点、三个节点那种然后用箭头模拟指针的移动。很多看起来复杂的指针操作画一遍就豁然开朗。两数相加这道题本质上就是“竖式加法 链表遍历 进位传递”三个知识点的组合。只要把这三个点拆开吃透以后再遇到类似的大数相加、链表合并、区间反转题目心里都会踏实很多。我在实际写这段代码的过程中最难忘的一次踩坑就是忘了处理最后的 carry导致 [9,9,9] [1] 这组用例输出 [0,0,0]查了半天才发现是循环条件少写了 carry。从那以后凡是带进位的题目我都会把“最后一个进位”当成一个独立的边界条件写进测试用例里。写代码前先写出三到五个测试用例再用代码去满足它们是个非常好的习惯。希望这篇拆解能帮你把这道经典题吃透。如果你在本地编译或者调试时遇到什么奇怪的问题不妨按着上面的思路一个个排查大多数问题都出在空指针、进位和内存管理这三件事上。祝刷题顺利面试顺利。