力扣第2题两数相加算得上是我入坑 C 刷题之后认真吃透的第一道链表题。之前看这题以为只是简单的“加一加”真正手动把两个逆序链表过一遍边界之后才发现里面藏了不少容易翻车的细节。这题在力扣热题 100 里排得很靠前也是很多面试官喜欢拿出来“热身”的题目。我已经用 C 实现过迭代、递归、原地修改三种写法也踩过调试环境、内存释放、空指针访问这些经典坑。这篇就把我自己的完整解题思路、C 代码、本地调试环境配置和排查经验一起写清楚给准备刷链表题的朋友做个参考。1. 题目解析两数相加到底在考什么1.1 题目原文与考点拆解题目本身非常简短。给你两个非空链表分别表示两个非负整数每个节点只存一位数字而且数字是按逆序存储的。所谓逆序就是链表的头节点对应数字的个位第二个节点对应十位依此类推。要求返回一个新的链表表示这两个数相加后的结果同样按逆序存储。举个例子最直观l1 [2, 4, 3]它表示整数 342l2 [5, 6, 4]它表示整数 465两数相加是 807所以返回的链表就是 [7, 0, 8]这不是一道难在算法上的题而是一道难在“把所有情况都想到”的题。核心考点有三个链表遍历是基本功哑节点和进位处理是技巧点边界条件考虑是否完整是区分度所在。很多人第一次写这题连题目都没理解透以为“把链表转成整数相加之后再转回来”就行结果不是溢出就是多此一举。后面我会专门说为什么不要在刷题场景里用这种偷懒方案。1.2 为什么用链表逆序存储数字其实是模拟竖式加法小时候做加法竖式时我们从个位开始对齐逐位相加满十进一。逆序链表最巧妙的地方就是让链表的头节点落在个位上两个链表从头开始同时走天然就是“低位对齐”。这和竖式加法的过程完全一致不需要像数组那样额外处理长度对齐。比如计算 342 465个位2 5 7记下 7进位 0十位4 6 10记下 0进位 1百位3 4 1 8记下 8进位 0对应链表操作就是同时遍历两个链表每轮取节点上的值相加再加上来自低位的进位。进位用一个变量保存下一轮继续带进去。这个思路理解了整道题就只剩翻译成代码的问题。1.3 为什么不建议转成整数再相加有的朋友一看“链表表示整数”第一反应是把链表还原成 int 或者 long long算完再转回链表。我一开始也这么想过但在实际刷题和面试场景下这种做法至少有三个问题。一是精度不够。链表可以很长题目虽然没说节点数量上限但力扣的极端测试用例会构造几十上百位的数字int 只有 32 位最大也就 21 亿多long long 到不了 922 京也扛不住几百位的大整数。你算到一半直接溢出后面全错。二是额外开销大。每遍历一次链表做一次累加再遍历一次结果做一次转换时间复杂度翻倍代码也绕。三是完全失去了这题想考察的“链表模拟加法”意义面试官基本不会认可这种写法。真正的做法是沿着链表一位一位处理像竖式加法一样把问题拆解成局部的小规模计算。2. C 实现两套能直接提交的代码2.1 迭代写法哑节点 进位循环我最早提交的版本就是迭代写法也是我认为最好理解、最适合做模板的一套。先定义一个哑节点 dummy 作为结果链表的头前哨好处是当链表为空时我们不用单独处理头指针为空的情况最后直接返回 dummy-next 就行。直接看代码/** * Definition for singly-linked list. * 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) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dummy new ListNode(0); ListNode* cur dummy; int carry 0; while (l1 ! nullptr || l2 ! nullptr || carry ! 0) { int sum carry; if (l1 ! nullptr) { sum l1-val; l1 l1-next; } if (l2 ! nullptr) { sum l2-val; l2 l2-next; } carry sum / 10; cur-next new ListNode(sum % 10); cur cur-next; } return dummy-next; } };这个实现的几个关键点我想拆开说一下。循环条件写成while (l1 || l2 || carry)意思很明确只要两个链表还有节点或者进位还不为 0就要继续生成新节点。为什么要带上 carry因为有一种很容易忽略的情况两个链表都走完了但最后一次相加产生了进位。比如 5 5 10最后要多出一个值为 1 的节点。如果循环条件漏了carry ! 0这个最高位就丢了。每一轮里先把上一轮留下的进位加到 sum 里。然后如果对应链表还有节点就取它的值并把指针向后移动。这里要注意l1 和 l2 的长度不一定相同所以两个 if 各自独立判断不能只判断一个就假设另一个也有。之后carry sum / 10当前节点值存sum % 10。比如 sum 是 16那这一位写 6进 1sum 是 20这一位写 0进 2。这个逻辑和十进制加法完全一致。至于为什么用new ListNode(sum % 10)而不是在栈上创建临时节点是因为力扣的返回要求是一个由调用方管理的链表栈上对象在函数返回时就析构了悬空指针必然导致运行错误。这是 C 刷链表题绕不开的内存管理问题后面我会再说。2.2 递归写法让调用栈帮你处理进位迭代写法的思路很直接但递归写法的代码会更短也能帮你练习“把问题分解成子问题”的思维。递归的核心想法是当前节点的值由本位的两个数和低位的进位决定然后剩下的部分交给递归来处理。class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry 0) { if (l1 nullptr l2 nullptr carry 0) { return nullptr; } int sum carry; if (l1 ! nullptr) { sum l1-val; } if (l2 ! nullptr) { sum l2-val; } ListNode* node new ListNode(sum % 10); node-next addTwoNumbers(l1 nullptr ? nullptr : l1-next, l2 nullptr ? nullptr : l2-next, sum / 10); return node; } };递归终止条件依旧是“链表走完且无进位”。每次递归返回当前节点然后通过node-next把子问题的结果串起来。这段代码很短但有一个小地方要注意如果只判断l1 nullptr l2 nullptr就返回但是恰巧 carry 不为 0最高位就会漏掉。相比之下迭代写法更贴近常规的思维流程递归写法适合在理解了核心逻辑之后再去体会。两种都必须能在纸上写出来因为面试官很可能问“你用迭代写一次再用递归写一次”或者“递归的空间复杂度是多少”。2.3 迭代和递归怎么选我自己的建议是刷题阶段先掌握迭代因为它在生产代码里更常见不容易出栈溢出问题。递归虽然代码简洁但每一层递归都会吃调用栈链表长度极端时可以考虑到空间复杂度不是 O(1)而是 O(mn)。力扣的测试不会因为递归栈溢出卡你但在面试里被追问时你要说得清楚。另外递归写法在返回值处理上更“隐式”。不少人第一次写递归会出现“new 出来的节点每次都被覆盖”的问题或者 return 之后没有正确 next。调试这种问题比迭代版本麻烦所以我个人建议在链表基本功还不稳的时候先用迭代建立“哑节点 遍历 连接”的肌肉记忆再拿递归做对比练习。3. 实操心得这些边界坑我全踩过3.1 边界情况核对清单写链表题最怕的就是“样例过了提交全红”。我吃过几次亏之后总结了一个习惯提交之前先按下面的清单逐项核对。一个链表为空。虽然题目说输入都是非空链表但函数内部可能处理到某个链表先走完的情况你不能访问空指针的 val。两个链表长度不同。比如 l1 [9, 9, 9, 9]l2 [1]短的先走完长的还剩三位最后一位还要考虑前面进位上来的值。结果长度比两个链表都长。典型例子是 999 1 1000最终链表是 [0, 0, 0, 1]最高位来自最后的 carry。结果为 0。l1 [0]l2 [0]返回的应该是 [0]而不是空链表。无进位情况。比如 1 2 3carry 全程为 0。我不建议靠脑子空想直接把这几组用例丢进本地测试里一次就能看到问题所在。3.2 内存管理new 出来的节点谁来释放这是 C 刷题和其他语言不太一样的地方。力扣的判题环境里你new ListNode出来的节点一般由平台统一回收你不需要也不应该在函数里手动 delete否则返回的链表就是悬空指针。但是如果你在本地跑测试函数那就得注意释放不然跑一万个用例就泄漏一万个节点。我在本地测试时会写一个deleteList辅助函数测试结束统一清理void deleteList(ListNode* head) { while (head ! nullptr) { ListNode* next head-next; delete head; head next; } }还有一个小细节大部分题解里会加的哑节点dummy也是new出来的如果返回的dummy-next和链表本身连在一起删除时也要保证不会重复 delete。我的习惯是让dummy始终指向返回链表的头前一个位置最后清理时从返回的头节点开始而不是从 dummy 开始这样不会重复释放。3.3 调试技巧构造链表和打印链表光在力扣网页里做题很难快速定位是哪个用例挂了。我在 VSCode 里自己搭了一个最小测试工程每次写完直接本地跑最关键的是要有一个构造链表和打印链表的工具函数。ListNode* createList(std::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; } void printList(ListNode* head) { while (head ! nullptr) { std::cout head-val; if (head-next ! nullptr) { std::cout - ; } head head-next; } std::cout std::endl; }有了这两个函数main 里可以写得很直观int main() { ListNode* l1 createList({2, 4, 3}); ListNode* l2 createList({5, 6, 4}); Solution solution; ListNode* result solution.addTwoNumbers(l1, l2); printList(result); // 期望输出7 - 0 - 8 }如果你比较懒可以用断言而不是打印写一个判断链表相等的函数一套用例跑下来哪个不通过一目了然。这就是本地测试带来的最大价值。4. 从力扣到本地C 刷题环境的配置实操4.1 VSCode 最小可用的 C 环境如果你也想在本地跑链表测试我建议直接用 VSCode MinGW-w64轻量也免费。这里只讲最小可用的配置。先装 C/C 扩展再装 MinGW-w64把g的 bin 目录加到系统 PATH 里。安装完之后打开终端验证一下。g --version能正常输出版本号就说明编译器没问题。然后新建一个目录把结构体定义、Solution 类、createList、printList、main 都放进去。编译运行直接走命令行即可g -stdc17 -g main.cpp -o main ./main如果代码报错就用 -g 参数生成调试信息配合 VSCode 的调试功能逐段断点。如果想在 VSCode 里按 F5 直接跑需要配置tasks.json和launch.json。tasks.json 里把编译命令写好launch.json 里选择 gdb 调试器exe 路径指向编译产物。这个配置我踩了不少坑最常见的现象是编译成功了但 launch 找不到 exe后来我把cwd和program都改成${workspaceFolder}拼接的绝对路径就稳定了。新手如果暂时不需要断点调试其实直接用命令行编译运行反而花的时间最少。4.2 编译通过但运行崩溃access violation 的排查思路有些朋友会遇到编译全部通过运行却直接崩溃Windows 下弹窗提示类似 access violation c0000005 的错误。这个错误码对应的就是野指针、空指针访问之类的问题。链表题里最容易触发的地方有三个一是循环里没有判断指针是不是 nullptr 就去取node-val二是函数返回了栈上对象的地址三是两个链表节点被迭代时错误地把l1指针和l2指针互相覆盖。我的排查顺序是先看崩溃信息发生在哪一行再用 gdb 或者 VSCode 断点观察是哪个指针为空。比如你在sum l1-val这一行崩溃多半就是 l1 已经走到 nullptr但循环条件判断错了。把 while 条件改成while (l1 || l2 || carry)然后每个取值前都做 if 判空这类崩溃基本就能消掉。还有一个我上了年纪才知道的坑Windows 下有些 C 代码在 Release 版没问题Debug 版崩溃那是因为 Debug 模式会填充未初始化内存暴露你没有初始化指针的问题。链表节点定义里构造函数已经把 val 和 next 都初始化了所以这个问题在这道题里不多见。4.3 缺运行库的坑Microsoft Visual C Redistributable本地跑 C 程序还可能碰到另一种诡异情况双击 exe 提示找不到 VCRUNTIME140.dll 或者 MSVCP140.dll。这不是你的代码有问题而是系统缺少 Microsoft Visual C 运行时库。很多从没装过 Visual Studio 的机器都会这样尤其学校机房、公司统一办公机。解决方式很简单去微软官网下载 Visual C Redistributable 2015-2022 的 x64 版本安装装完一般就能跑。另外一个类似问题是在 MinGW 环境下提示缺少 libstdc-6.dll这通常是因为 g 的 bin 目录没有在 PATH 里或者 exe 发布到了别的机器。把 MinGW 的 bin 目录加进 PATH或者直接把 dll 拷贝到 exe 同目录都可以。遇到这种环境问题不用慌它不是算法的问题但会真实打断你的刷题节奏。我现在每次换电脑配置开发环境都会先把编译器、运行库、终端验证这三件事一次性做完再开始写题。4.4 用本地测试用例验证边界在本地写测试时我建议把边界用例全列出来直接作为一道“题目”来跑。我用一个简单的方式组织每种用例一行跑完打印 PASS 或 FAIL。比如[2,4,3] [5,6,4]应该等于[7,0,8][0] [0]应该等于[0][9,9] [1]应该等于[0,0,1][9,9,9,9] [1]应该等于[0,0,0,0,1]这样每次改完代码一键全跑不用反复去力扣网页提交。我发现很多刷题新手把“写代码”和“验证代码”混在一起写完了才去力扣跑跑挂了再改效率很低。在本地把边界验证完再提交基本上就是一遍过。5. 延伸与总结这道题的进阶价值5.1 相似题目横向对比从两数相加到大数运算一道题吃透之后一定要做关联扩展。力扣里跟两数相加直接相关的题目有好几道思路都脱胎于这道题。第 415 题字符串相加。两个字符串表示非负整数需要返回字符串形式的结果。思路和链表完全一致只是把链表节点换成字符注意进位一样要带。第 67 题二进制求和。从十进制变成二进制sum 满 2 进 1核心框架仍然是一模一样的。第 445 题两数相加 II。数字是正序存储的不能再直接从头遍历因为高位在前需要借助反转链表或者栈。它本质上还是这道题的变种只是多了一步预处理。我把这几个题放在同一天练习做完就发现只要掌握了“遍历 进位 判断边界”这套模板不管换什么进制、什么数据结构都能很快迁移。这也是为什么我觉得第 2 题值得认真多写几遍。5.2 面试加分点空间优化和代码可读性第 2 题基础版的时间复杂度是 O(max(m, n))空间复杂度是 O(max(m, n))因为你新建了一条链表。如果被面试官追问能不能优化空间你可以说直接在原链表上修改这样空间可以做到 O(1)前提是允许改输入的链表。具体做法是选较长的那条链表作为结果载体把较短链表的值逐个累加进去同时处理进位返回长链表的头节点。思路不难但代码细节比新建链表要复杂因为要特别处理最后新增一个节点的情况。面试时不一定要真的写出来但能说出思路也是一种加分。真正加分的往往不是花哨的技巧而是代码可读性。变量名起清楚循环条件写成while (l1 ! nullptr || l2 ! nullptr || carry ! 0)而不是while (l1 || l2 || carry)这种细节在讲代码的时候很加分。力扣上写题主要是自己看但面试时这些习惯会成为你的“隐性优势”。5.3 我的复盘心得怎么刷题效率更高这道题我前前后后写过五遍。第一遍看书上题解照着敲似懂非懂第二遍关掉题解自己写卡在循环条件和进位处理第三遍用递归写终于理解每一位是如何串联起来的第四遍开始写本地测试把边界用例验证整齐第五遍是为了给这篇分享整理素材重新优化了一遍代码。每一次的收获都不一样所以我很建议刷题不要“刷完就丢”。具体到第 2 题我实际使用的做题顺序是这样的先花三分钟读题并自己推一遍示例然后用纸笔模拟一个长用例比如 999 加 1明确最终结果比两个输入都长接着在编辑器里写第一版迭代代码本地跑边界用例全部通过后再花五分钟写递归版本比较两种写法的差异最后去力扣提交。对大部分准备面试的朋友来说这道题做到“迭代随手写、递归能讲清、边界不漏”就已经完全合格了。我在实际教学和帮人 review 代码时发现大多数人真正的问题不是不会写 while 循环而是不敢动手把问题拆解成“当前位怎么算”和“下一位怎么算”。第 2 题恰恰是最适合训练这种拆解能力的题目之一。你要是能把这道题的代码写到连自己都挑不出毛病后面的链表反转、合并有序链表、环形链表检测都会顺畅很多。