力扣的第2题《两数相加》是一道很有代表性的链表题刚好卡在入门和进阶的中间位置。第1题用哈希表五分钟能过第2题就要求你正儿八经写链表遍历、处理进位、考虑边界这对刚接触C的刷题新手来说算是一道实打实的分水岭。我自己当年刷这道题的时候代码写完一提交信心满满结果Wrong Answer原因就是最高位进位没处理。这篇文章就把这道题的来龙去脉、C实现细节、我踩过的坑和进阶玩法都摊开来讲给想好好啃C链表的朋友做个参考。1. 先看懂题目逆序存储的链表到底在表达什么1.1 题面拆解两个“反着写”的数字这道题的核心并不复杂给了两个非空链表每个节点存一位数字数字本身是逆序存储的。什么叫逆序就是链表的头节点是个位第二个节点是十位第三个节点是百位以此类推。举个例子数字 807 在链表里是 7 - 0 - 8数字 41 在链表里是 1 - 4。那么这两个数相加的结果是 848输出链表就应该是 8 - 4 - 8。很多人第一次看到“逆序”两个字容易懵觉得这是故意为难人。但实际上这恰恰是题目的善意设计。因为人工算加法的时候我们也是从个位开始对齐逐位相加有进位就往高位进这正好和链表的遍历方向一致——从头部开始遍历就是从个位开始遍历。这里要提一个关键点为什么不用数组、不用整数类型偏偏用链表因为题目里的数字可以非常大大到没有任何内置整数类型能装下。C里的long long最多也就64位而链表可以无限延长每一位单独一个节点理论上可以表示任意长的数字。所以链表在这里不是炫技而是承载大数运算的合理数据结构。1.2 逆序存储的深意与加法流程天然对齐试想一下如果题目给的是正序链表也就是头节点是最高位那我们必须得先走到链表的末尾才能开始对齐个位要么用栈要么先反转链表绕一个很大的弯。而逆序存储直接让头节点就是个位两链表的头对齐就是个位对齐遍历一个节点就完成一位的加法非常自然。这个设计启示可以记下来链表的头节点不一定代表“数字的最高位”题目怎么定义你就怎么用它不要惯性思维地认为“开头就是大头”。刷链表题的时候先想清楚头节点代表什么往往能少走很多弯路。1.3 从“暴力解法”到“按位模拟”的思路转变有些刚开始刷题的朋友会想能不能先把链表转成long long两个数加起来后再转回链表这样写的代码很短但这有两个致命问题一是数字太大时会溢出直接得到错误结果二是这违背了题目考察链表操作的初衷。力扣的OJOnline Judge测试用例里一定会塞入超出long long范围的数字暴力解法在测试用例面前就是送人头。所以正确思路是模拟人工加法同时遍历两个链表对应位相加产生进位就标记下一位多加上这个进位值。听起来简单但三个细节要抠清楚——两个链表长度不一样怎么办、遍历完了还有进位怎么办、其中一个链表为空怎么办。这些细节才是这道题真正的考点。2. 核心思路手算加法的算法化过程2.1 从个位同步遍历两个链表一起走我们先理清最基础的操作。假设两个链表叫l1和l2各有一个头指针。开始循环之前先准备一个carry变量用来存进位初始值为0。然后进入循环体取l1当前节点的值如果l1已经走到头就取0。取l2当前节点的值同理如果走到头了就取0。计算sum val1 val2 carry。新节点的值就是sum % 10个位。新的进位carry sum / 10十位。用new ListNode(sum % 10)创建新节点接到结果链表的尾部。l1和l2各自向后移动一位前提是它们不为空。就这么循环下去直到两个链表都遍历完毕且进位为0。这里有一个容易写成死循环的陷阱如果循环条件是while (l1 ! nullptr || l2 ! nullptr)那么循环体里取节点值之前必须判空否则短的链表走完后再访问l1-val就是空指针访问程序直接崩溃。所以每次取值都要先判断当前指针是否为空。2.2 进位变量的生命周期加法器的灵魂进位carry是整个算法的灵魂。它只有两个取值0或1。因为两个一位数相加最大是9918加进位1最多是19所以进位不可能超过1。这一点很多人能想到但实际写代码时却容易忽略循环结束后遗留的进位。什么情况会产生“遗留进位”比如 5 - 6 和 5 - 4 相加个位5510进位1新节点存0十位64111进位1新节点存1此时两个链表都遍历完了但还要再创建一个值为1的节点表示百位。如果循环条件里没考虑carry ! 0循环在这里就结束了结果会少一位答案错误。我的建议是循环条件直接写成while (l1 ! nullptr || l2 ! nullptr || carry ! 0)这样进位判断在循环条件里一并解决代码简洁也不会漏。这是我在踩过一次坑之后固定下来的写法。2.3 哑节点dummy node链表题中的第一工具新建一个结果链表的时候最常见的操作就是不断往尾部追加节点。但麻烦在于结果链表的头节点在循环开始前是未知的遍历过程中才慢慢生成。如果不做处理每次追加节点都要判断“这是不是第一个节点”代码会多出很多分支判断。解法就是使用哑节点dummy nodeListNode* dummy new ListNode(0); ListNode* cur dummy;之后在循环里只需要不断执行cur-next new ListNode(...); cur cur-next;完全不用管是不是第一个节点。循环结束后dummy-next就是结果链表的真实头节点直接返回它即可。哑节点的本质是用一个占位的节点省去对头节点的特判。这个技巧在几乎所有链表题里都好使——删除节点、合并链表、反转链表都能用。建议把这个技巧当成肌肉记忆一样练成本能。2.4 边界条件清单写代码前先过一遍在动手写代码之前我建议先把所有边界条件列出来避免事后亡羊补牢。这道题的边界条件包括场景处理方式两个链表长度不同短链表走完后对应位取0其中一个链表为空直接按0处理但仍要处理进位最高位产生进位循环结束后补一个值为1的新节点两个链表都为空测试用例不会给但本地测试可能出现返回空链表或0节点取决于题目约定把边界条件列成一个清单放在脑子里或纸上比直接埋头写代码要稳妥得多。因为循环体的逻辑本身不难难的是所有异常情况都要照顾到。3. C代码实现一个能直接提交的版本3.1 力扣的结构体定义和接口签名在力扣做题链表节点结构体是平台已经定义好的你只需要直接用/** * 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(int x)这个版本。3.2 核心循环的两种写法对比写法一把进位放进循环条件最简洁也是我推荐的写法。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; } cur-next new ListNode(sum % 10); cur cur-next; carry sum / 10; } return dummy-next; } };写法二循环条件只判断l1和l2循环结束后单独处理进位。这种写法逻辑上更“传统”但多一步收尾工作代码会稍长。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) { int sum carry; if (l1 ! nullptr) { sum l1-val; l1 l1-next; } if (l2 ! nullptr) { sum l2-val; l2 l2-next; } cur-next new ListNode(sum % 10); cur cur-next; carry sum / 10; } if (carry ! 0) { cur-next new ListNode(carry); } return dummy-next; } };两种写法在结果上完全等价核心区别在于谁来做最后的收尾。写法一更不容易遗漏写出bug的概率更低我建议新手直接采用写法一。写法二的好处是逻辑更直观适合当作第一版写然后改成写法一。3.3 时间复杂度和空间复杂度分析这道题的时间复杂度很容易分析两个链表各被遍历一遍循环次数等于较长链表的长度加上最多一次进位处理所以是O(max(m, n))其中m和n分别是两个链表的长度。空间复杂度就有讲究了。如果只算新创建的结果链表需要O(max(m, n))的空间。如果不算结果链表本身只算额外辅助空间那就是O(1)——因为我们只用了dummy、cur、carry这几个固定变量。力扣的复杂度分析通常把结果链表本身也算进去所以标准答案是O(max(m, n))。这里顺带提一下本地测试的注意点力扣平台会自动回收内存你在本地用new创建节点后如果是在自己写的测试工程里跑记得写一个释放链表的函数否则内存泄漏。这个问题我在第4章会展开讲。4. 实战踩坑我在这道题上犯过的错4.1 最高位进位不是“可选项”是必选项我第一次提交这道题时循环条件用的是while (l1 ! nullptr || l2 ! nullptr)循环体里正常处理进位但没在循环结束后补进位判断。当时想着“两个链表都走完了肯定完事了”结果遇到9 - 9加1这个用例输出是0 - 0正确答案是0 - 0 - 1少了最高位的1。这个bug在本地测试时非常容易漏掉因为你可能恰好没测“最高位相加后产生新进位”的用例。我当时是随便构造了一组数据看出结果不对又把循环打印加进去一步步模拟才定位到问题。从那以后我养成一个习惯链表题提交前先手动构造几组边界用例包括两个链表长度差很悬殊、最高位连续进位、结果全是0等情况。最高位进位不是这道题的特例而是所有按位加法类问题的共性考点。4.2 指针移动顺序与空指针访问还有一个很经典的错误就是取数之后忘了移动指针或者取数之前先移了指针导致当前节点的值丢失。比如有人会写while (l1 ! nullptr || l2 ! nullptr) { int sum carry; if (l1 ! nullptr) { l1 l1-next; // 先移动再取val错了 sum l1-val; } // ... }这样写l1已经指向next了再取l1-val取到的是下一个节点的值而当前节点的值已经被跳过去了。正确顺序一定是先取l1-val再把l1 l1-next。另一个新手常犯的问题是访问空指针。在循环里l1和l2各自可能已经走到nullptr所以取值前必须判空。有人会写sum l1-val; l1 l1-next;但不判空如果l1比l2短短的遍历完之后下一次循环l1是nullptr访问l1-val直接段错误。4.3 本地调试自己构造测试用例和释放内存力扣的OJ把环境都配好了但如果你要在本地用VS Code调试就得自己写一点辅助代码。我通常会在main函数里写一个createList函数用数组快速构建链表再写一个printList打印链表这样就能逐行调试。#include iostream #include vector using namespace std; // ... ListNode 结构体定义 ... ListNode* createList(const vectorint vals) { ListNode* dummy new ListNode(0); ListNode* cur dummy; for (int val : vals) { cur-next new ListNode(val); cur cur-next; } return dummy-next; } void printList(ListNode* head) { while (head ! nullptr) { cout head-val; if (head-next ! nullptr) cout - ; head head-next; } cout endl; } void freeList(ListNode* head) { while (head ! nullptr) { ListNode* next head-next; delete head; head next; } } int main() { ListNode* l1 createList({9, 9}); ListNode* l2 createList({1}); Solution solution; ListNode* result solution.addTwoNumbers(l1, l2); printList(result); freeList(l1); freeList(l2); freeList(result); return 0; }这里有一个非常重要的内存管理细节在力扣上做题不用考虑释放节点但本地练习必须写freeList否则每跑一个用例就是一批内存泄漏。很多人在本地跑LeetCode代码跑了几百个用例之后内存占用越来越高就是这个原因。在本地测试时记得把l1、l2和结果链表都delete掉。VS Code配置C环境也是很多新手卡住的地方。简单来说装好MinGW或者MSVC编译器配置好tasks.json和launch.json就可以F5启动调试了。如果你配置的时候遇到头文件找不到、编译器路径不对、launch配置错误这些问题网上有大量教程可查我这里不再展开但提醒一句环境的坑和算法的坑是两码事不要在环境上耗太久能跑通就行。5. 进阶思考这道题不止一种解法5.1 原地修改链表把结果存进较长链表基础解法需要创建一条全新的链表。但如果你想省空间完全可以复用较长链表的节点把结果直接写在原链表上。思路是找出l1和l2中较长的那个遍历时直接修改它的节点值最后返回较长链表的头指针即可。这里的核心难点是如果最终进位使得结果比原链表多一位你需要在链表尾部追加一个节点。也就是说虽然大部分节点是复用的但最后一个进位节点仍需新建。空间复杂度理论上可以降到O(1)如果不算追加的那个节点但代码复杂度会上升因为你要在循环前先判断哪条链表更长循环中还要时刻判断当前节点是否属于原来的短链表——如果短链表已经走完了接下来的节点就直接用长链表现有的节点存值。我个人在实际项目中并不推荐这种极致的空间优化因为力扣的判题系统不在乎你省那几百字节的内存但代码可读性会显著下降。不过这个思路值得了解因为它展示了链表操作的一个重要技巧节点不是只能“新建”也可以“修改复用”。5.2 延伸变形正序链表、大数相乘、循环链表这道题的变体非常多。如果题目改成正序存储比如8 - 0 - 7表示807那最直接的办法是先用反转链表的技巧把两个链表反转成逆序再用这道题的逻辑相加最后把结果反转回去。这里有个陷阱反转后原链表被破坏如果你还需要原链表做后续操作就先复制一份再反转。链表题的经典套路就是这样——反转、快慢指针、哑节点、递归几样工具反复组合。另一个变体是大数相乘比如链表表示的12345乘链表表示的6789。这实际上是循环做多次加法每次移位相加。力扣上有类似的高频题核心思路也是这道题的延伸只是需要额外处理偏移和累加。此外如果链表有环问题会更复杂但这属于后话了。先说结论把第2题吃透等于你掌握了链表遍历、哑节点、进位模拟、边界处理这一整套基本技能后续很多题都能复用。5.3 从这道题延伸出来的C基本功清单刷完这道题我建议你把下面这几个C知识点同步补上结构体与构造函数ListNode的三种构造函数分别怎么用值初始化、指针初始化。指针与空指针什么时候判空判空后怎么处理空指针访问的危害。动态内存分配new和delete的配对使用内存泄漏的基本概念。循环与条件控制while循环的结束条件设计sum % 10和sum / 10的用法。函数返回值与引用返回ListNode*意味着什么和返回ListNode有什么区别。对C新手来说这些知识点看起来零散但链表题把它们串在了一起。比如说sum % 10是取个位sum / 10是取进位这两步一写整数的取模和除法运算就自然熟悉了。再比如ListNode* cur dummy;这行代码就是指针变量赋值的典型应用。把这题做完后你对“指针到底指向谁”这个概念的理解会比纯看教程深刻得多。我个人的体会是刷题和学语言是一个相互促进的过程。不要想着先把C完全学明白了再开始刷题那会拖得很久也别指望光刷题就能把语言融会贯通。最好的节奏是先掌握基础的语法数组、循环、指针的皮毛然后直接开刷刷的过程中遇到不懂的概念再回头看教程。第2题这个难度恰恰是开启这个循环的绝佳入口。这道题一遍跑不通很正常跑通了之后后面的链表题你会发现自己上手快得多。 力扣两数相加C++解法：链表遍历与进位处理实战
力扣的第2题《两数相加》是一道很有代表性的链表题刚好卡在入门和进阶的中间位置。第1题用哈希表五分钟能过第2题就要求你正儿八经写链表遍历、处理进位、考虑边界这对刚接触C的刷题新手来说算是一道实打实的分水岭。我自己当年刷这道题的时候代码写完一提交信心满满结果Wrong Answer原因就是最高位进位没处理。这篇文章就把这道题的来龙去脉、C实现细节、我踩过的坑和进阶玩法都摊开来讲给想好好啃C链表的朋友做个参考。1. 先看懂题目逆序存储的链表到底在表达什么1.1 题面拆解两个“反着写”的数字这道题的核心并不复杂给了两个非空链表每个节点存一位数字数字本身是逆序存储的。什么叫逆序就是链表的头节点是个位第二个节点是十位第三个节点是百位以此类推。举个例子数字 807 在链表里是 7 - 0 - 8数字 41 在链表里是 1 - 4。那么这两个数相加的结果是 848输出链表就应该是 8 - 4 - 8。很多人第一次看到“逆序”两个字容易懵觉得这是故意为难人。但实际上这恰恰是题目的善意设计。因为人工算加法的时候我们也是从个位开始对齐逐位相加有进位就往高位进这正好和链表的遍历方向一致——从头部开始遍历就是从个位开始遍历。这里要提一个关键点为什么不用数组、不用整数类型偏偏用链表因为题目里的数字可以非常大大到没有任何内置整数类型能装下。C里的long long最多也就64位而链表可以无限延长每一位单独一个节点理论上可以表示任意长的数字。所以链表在这里不是炫技而是承载大数运算的合理数据结构。1.2 逆序存储的深意与加法流程天然对齐试想一下如果题目给的是正序链表也就是头节点是最高位那我们必须得先走到链表的末尾才能开始对齐个位要么用栈要么先反转链表绕一个很大的弯。而逆序存储直接让头节点就是个位两链表的头对齐就是个位对齐遍历一个节点就完成一位的加法非常自然。这个设计启示可以记下来链表的头节点不一定代表“数字的最高位”题目怎么定义你就怎么用它不要惯性思维地认为“开头就是大头”。刷链表题的时候先想清楚头节点代表什么往往能少走很多弯路。1.3 从“暴力解法”到“按位模拟”的思路转变有些刚开始刷题的朋友会想能不能先把链表转成long long两个数加起来后再转回链表这样写的代码很短但这有两个致命问题一是数字太大时会溢出直接得到错误结果二是这违背了题目考察链表操作的初衷。力扣的OJOnline Judge测试用例里一定会塞入超出long long范围的数字暴力解法在测试用例面前就是送人头。所以正确思路是模拟人工加法同时遍历两个链表对应位相加产生进位就标记下一位多加上这个进位值。听起来简单但三个细节要抠清楚——两个链表长度不一样怎么办、遍历完了还有进位怎么办、其中一个链表为空怎么办。这些细节才是这道题真正的考点。2. 核心思路手算加法的算法化过程2.1 从个位同步遍历两个链表一起走我们先理清最基础的操作。假设两个链表叫l1和l2各有一个头指针。开始循环之前先准备一个carry变量用来存进位初始值为0。然后进入循环体取l1当前节点的值如果l1已经走到头就取0。取l2当前节点的值同理如果走到头了就取0。计算sum val1 val2 carry。新节点的值就是sum % 10个位。新的进位carry sum / 10十位。用new ListNode(sum % 10)创建新节点接到结果链表的尾部。l1和l2各自向后移动一位前提是它们不为空。就这么循环下去直到两个链表都遍历完毕且进位为0。这里有一个容易写成死循环的陷阱如果循环条件是while (l1 ! nullptr || l2 ! nullptr)那么循环体里取节点值之前必须判空否则短的链表走完后再访问l1-val就是空指针访问程序直接崩溃。所以每次取值都要先判断当前指针是否为空。2.2 进位变量的生命周期加法器的灵魂进位carry是整个算法的灵魂。它只有两个取值0或1。因为两个一位数相加最大是9918加进位1最多是19所以进位不可能超过1。这一点很多人能想到但实际写代码时却容易忽略循环结束后遗留的进位。什么情况会产生“遗留进位”比如 5 - 6 和 5 - 4 相加个位5510进位1新节点存0十位64111进位1新节点存1此时两个链表都遍历完了但还要再创建一个值为1的节点表示百位。如果循环条件里没考虑carry ! 0循环在这里就结束了结果会少一位答案错误。我的建议是循环条件直接写成while (l1 ! nullptr || l2 ! nullptr || carry ! 0)这样进位判断在循环条件里一并解决代码简洁也不会漏。这是我在踩过一次坑之后固定下来的写法。2.3 哑节点dummy node链表题中的第一工具新建一个结果链表的时候最常见的操作就是不断往尾部追加节点。但麻烦在于结果链表的头节点在循环开始前是未知的遍历过程中才慢慢生成。如果不做处理每次追加节点都要判断“这是不是第一个节点”代码会多出很多分支判断。解法就是使用哑节点dummy nodeListNode* dummy new ListNode(0); ListNode* cur dummy;之后在循环里只需要不断执行cur-next new ListNode(...); cur cur-next;完全不用管是不是第一个节点。循环结束后dummy-next就是结果链表的真实头节点直接返回它即可。哑节点的本质是用一个占位的节点省去对头节点的特判。这个技巧在几乎所有链表题里都好使——删除节点、合并链表、反转链表都能用。建议把这个技巧当成肌肉记忆一样练成本能。2.4 边界条件清单写代码前先过一遍在动手写代码之前我建议先把所有边界条件列出来避免事后亡羊补牢。这道题的边界条件包括场景处理方式两个链表长度不同短链表走完后对应位取0其中一个链表为空直接按0处理但仍要处理进位最高位产生进位循环结束后补一个值为1的新节点两个链表都为空测试用例不会给但本地测试可能出现返回空链表或0节点取决于题目约定把边界条件列成一个清单放在脑子里或纸上比直接埋头写代码要稳妥得多。因为循环体的逻辑本身不难难的是所有异常情况都要照顾到。3. C代码实现一个能直接提交的版本3.1 力扣的结构体定义和接口签名在力扣做题链表节点结构体是平台已经定义好的你只需要直接用/** * 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(int x)这个版本。3.2 核心循环的两种写法对比写法一把进位放进循环条件最简洁也是我推荐的写法。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; } cur-next new ListNode(sum % 10); cur cur-next; carry sum / 10; } return dummy-next; } };写法二循环条件只判断l1和l2循环结束后单独处理进位。这种写法逻辑上更“传统”但多一步收尾工作代码会稍长。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) { int sum carry; if (l1 ! nullptr) { sum l1-val; l1 l1-next; } if (l2 ! nullptr) { sum l2-val; l2 l2-next; } cur-next new ListNode(sum % 10); cur cur-next; carry sum / 10; } if (carry ! 0) { cur-next new ListNode(carry); } return dummy-next; } };两种写法在结果上完全等价核心区别在于谁来做最后的收尾。写法一更不容易遗漏写出bug的概率更低我建议新手直接采用写法一。写法二的好处是逻辑更直观适合当作第一版写然后改成写法一。3.3 时间复杂度和空间复杂度分析这道题的时间复杂度很容易分析两个链表各被遍历一遍循环次数等于较长链表的长度加上最多一次进位处理所以是O(max(m, n))其中m和n分别是两个链表的长度。空间复杂度就有讲究了。如果只算新创建的结果链表需要O(max(m, n))的空间。如果不算结果链表本身只算额外辅助空间那就是O(1)——因为我们只用了dummy、cur、carry这几个固定变量。力扣的复杂度分析通常把结果链表本身也算进去所以标准答案是O(max(m, n))。这里顺带提一下本地测试的注意点力扣平台会自动回收内存你在本地用new创建节点后如果是在自己写的测试工程里跑记得写一个释放链表的函数否则内存泄漏。这个问题我在第4章会展开讲。4. 实战踩坑我在这道题上犯过的错4.1 最高位进位不是“可选项”是必选项我第一次提交这道题时循环条件用的是while (l1 ! nullptr || l2 ! nullptr)循环体里正常处理进位但没在循环结束后补进位判断。当时想着“两个链表都走完了肯定完事了”结果遇到9 - 9加1这个用例输出是0 - 0正确答案是0 - 0 - 1少了最高位的1。这个bug在本地测试时非常容易漏掉因为你可能恰好没测“最高位相加后产生新进位”的用例。我当时是随便构造了一组数据看出结果不对又把循环打印加进去一步步模拟才定位到问题。从那以后我养成一个习惯链表题提交前先手动构造几组边界用例包括两个链表长度差很悬殊、最高位连续进位、结果全是0等情况。最高位进位不是这道题的特例而是所有按位加法类问题的共性考点。4.2 指针移动顺序与空指针访问还有一个很经典的错误就是取数之后忘了移动指针或者取数之前先移了指针导致当前节点的值丢失。比如有人会写while (l1 ! nullptr || l2 ! nullptr) { int sum carry; if (l1 ! nullptr) { l1 l1-next; // 先移动再取val错了 sum l1-val; } // ... }这样写l1已经指向next了再取l1-val取到的是下一个节点的值而当前节点的值已经被跳过去了。正确顺序一定是先取l1-val再把l1 l1-next。另一个新手常犯的问题是访问空指针。在循环里l1和l2各自可能已经走到nullptr所以取值前必须判空。有人会写sum l1-val; l1 l1-next;但不判空如果l1比l2短短的遍历完之后下一次循环l1是nullptr访问l1-val直接段错误。4.3 本地调试自己构造测试用例和释放内存力扣的OJ把环境都配好了但如果你要在本地用VS Code调试就得自己写一点辅助代码。我通常会在main函数里写一个createList函数用数组快速构建链表再写一个printList打印链表这样就能逐行调试。#include iostream #include vector using namespace std; // ... ListNode 结构体定义 ... ListNode* createList(const vectorint vals) { ListNode* dummy new ListNode(0); ListNode* cur dummy; for (int val : vals) { cur-next new ListNode(val); cur cur-next; } return dummy-next; } void printList(ListNode* head) { while (head ! nullptr) { cout head-val; if (head-next ! nullptr) cout - ; head head-next; } cout endl; } void freeList(ListNode* head) { while (head ! nullptr) { ListNode* next head-next; delete head; head next; } } int main() { ListNode* l1 createList({9, 9}); ListNode* l2 createList({1}); Solution solution; ListNode* result solution.addTwoNumbers(l1, l2); printList(result); freeList(l1); freeList(l2); freeList(result); return 0; }这里有一个非常重要的内存管理细节在力扣上做题不用考虑释放节点但本地练习必须写freeList否则每跑一个用例就是一批内存泄漏。很多人在本地跑LeetCode代码跑了几百个用例之后内存占用越来越高就是这个原因。在本地测试时记得把l1、l2和结果链表都delete掉。VS Code配置C环境也是很多新手卡住的地方。简单来说装好MinGW或者MSVC编译器配置好tasks.json和launch.json就可以F5启动调试了。如果你配置的时候遇到头文件找不到、编译器路径不对、launch配置错误这些问题网上有大量教程可查我这里不再展开但提醒一句环境的坑和算法的坑是两码事不要在环境上耗太久能跑通就行。5. 进阶思考这道题不止一种解法5.1 原地修改链表把结果存进较长链表基础解法需要创建一条全新的链表。但如果你想省空间完全可以复用较长链表的节点把结果直接写在原链表上。思路是找出l1和l2中较长的那个遍历时直接修改它的节点值最后返回较长链表的头指针即可。这里的核心难点是如果最终进位使得结果比原链表多一位你需要在链表尾部追加一个节点。也就是说虽然大部分节点是复用的但最后一个进位节点仍需新建。空间复杂度理论上可以降到O(1)如果不算追加的那个节点但代码复杂度会上升因为你要在循环前先判断哪条链表更长循环中还要时刻判断当前节点是否属于原来的短链表——如果短链表已经走完了接下来的节点就直接用长链表现有的节点存值。我个人在实际项目中并不推荐这种极致的空间优化因为力扣的判题系统不在乎你省那几百字节的内存但代码可读性会显著下降。不过这个思路值得了解因为它展示了链表操作的一个重要技巧节点不是只能“新建”也可以“修改复用”。5.2 延伸变形正序链表、大数相乘、循环链表这道题的变体非常多。如果题目改成正序存储比如8 - 0 - 7表示807那最直接的办法是先用反转链表的技巧把两个链表反转成逆序再用这道题的逻辑相加最后把结果反转回去。这里有个陷阱反转后原链表被破坏如果你还需要原链表做后续操作就先复制一份再反转。链表题的经典套路就是这样——反转、快慢指针、哑节点、递归几样工具反复组合。另一个变体是大数相乘比如链表表示的12345乘链表表示的6789。这实际上是循环做多次加法每次移位相加。力扣上有类似的高频题核心思路也是这道题的延伸只是需要额外处理偏移和累加。此外如果链表有环问题会更复杂但这属于后话了。先说结论把第2题吃透等于你掌握了链表遍历、哑节点、进位模拟、边界处理这一整套基本技能后续很多题都能复用。5.3 从这道题延伸出来的C基本功清单刷完这道题我建议你把下面这几个C知识点同步补上结构体与构造函数ListNode的三种构造函数分别怎么用值初始化、指针初始化。指针与空指针什么时候判空判空后怎么处理空指针访问的危害。动态内存分配new和delete的配对使用内存泄漏的基本概念。循环与条件控制while循环的结束条件设计sum % 10和sum / 10的用法。函数返回值与引用返回ListNode*意味着什么和返回ListNode有什么区别。对C新手来说这些知识点看起来零散但链表题把它们串在了一起。比如说sum % 10是取个位sum / 10是取进位这两步一写整数的取模和除法运算就自然熟悉了。再比如ListNode* cur dummy;这行代码就是指针变量赋值的典型应用。把这题做完后你对“指针到底指向谁”这个概念的理解会比纯看教程深刻得多。我个人的体会是刷题和学语言是一个相互促进的过程。不要想着先把C完全学明白了再开始刷题那会拖得很久也别指望光刷题就能把语言融会贯通。最好的节奏是先掌握基础的语法数组、循环、指针的皮毛然后直接开刷刷的过程中遇到不懂的概念再回头看教程。第2题这个难度恰恰是开启这个循环的绝佳入口。这道题一遍跑不通很正常跑通了之后后面的链表题你会发现自己上手快得多。