LeetCode热题100里两数相加几乎是我见过最适合用来练链表基本功的一道题。题目本身不难但能把Python、C语言、JAVA语言三种解法都写明白的人通常对指针、引用和边界条件的理解已经上了一个台阶。今天我把这道题从思路到三种语言实现完整拆一遍顺便把我在刷题和面试时踩过的坑都交代清楚。不管你是刚入门准备秋招还是想巩固链表基础这篇文章都值得你跟着敲一遍。1. 题目拆解与考点分析1.1 题目到底在考什么原题给的是两个非空链表表示两个非负整数。每个节点只存一位数字数字按照逆序存储也就是链表头对应数字的最低位。要求把两个数相加结果同样用逆序链表返回。说白了这就是小学数学竖式加法只不过把数字拆成了链表。核心要处理三件事链表怎么遍历。两个链表都要从头走到尾谁短谁先结束。进位怎么传播。每一位相加的结果可能超过9需要把十位上的1带到下一位。边界条件怎么兜底。两个链表长度不同、最后一位相加后还有进位、链表只有一个节点且值为0这些情况一个都不能漏。很多人第一眼觉得这题简单但一提交就发现报错。原因在于它考的并不是“会不会遍历链表”而是“能不能把循环条件和边界处理写干净”。面试官也特别喜欢在这道题后面追问如果两个链表很长很长怎么办如果最后还有进位怎么办能不能不用额外空间这些问题比答案本身更有价值。1.2 一看就会、一写就废的三个坑第一个坑是低位对齐。题目把数字逆序存储链表头就是最低位所以直接从头遍历两个链表的指针对齐了不需要像正序存储那样先反转链表。这是题目设计上的善意但很多人没意识到反而自己绕弯路去反转。第二个坑是最后进位。比如 99 1链表分别是 [9,9] 和 [1]。遍历完第一个节点9110当前位写0进位1遍历第二个节点90110当前位写0进位1循环结束后不能直接返回因为还多了一个进位1必须新建一个节点存1结果才会是 [0,0,1]也就是100。第三个坑是空指针。当一个链表已经遍历完另一个链表可能还有节点。比如 [1,8] 和 [0]l2走完时l1还剩一个8。如果循环条件里只写了while l1 and l2那这个8就会被丢掉。正确写法是while l1 or l2 or carry只要还有链表没走完、或者进位没清空循环就得继续。我在本地调试时最常用的一组测试用例是l1 [9,9,9,9,9,9,9]l2 [9,9,9,9]。期望结果是[8,9,9,9,0,0,0,1]也就是 9999999 9999 10009998。这个用例中间有一串连续的0进位一旦处理错结果立刻就不对比普通用例好用得多。2. Python实现从能跑到优雅2.1 迭代写法先保证跑通先给最朴素也最稳的版本。Python写链表题最舒服的一点是节点定义都帮你写好了不用管内存直接操作对象即可。class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]: dummy ListNode() cur dummy carry 0 while l1 or l2 or carry: total carry if l1: total l1.val l1 l1.next if l2: total l2.val l2 l2.next cur.next ListNode(total % 10) cur cur.next carry total // 10 return dummy.next这个版本有几个细节值得说。首先是dummy哨兵节点它本身不存有效数据只是为了统一“第一个节点”和“后续节点”的插入逻辑。没有它的话你得先判断result是不是 None代码会多出一段特判。第二个关键是循环条件里的carry。把进位写进条件就不用在循环结束后再补一段if carry: cur.next ListNode(carry)。这是我自己比较喜欢的写法少一条分支就少一个出错点。第三个关键是l1 l1.next一定要放在if l1内部。有人图省事写成l1 l1 and l1.next虽然也能跑但可读性差不推荐在面试里秀这种写法。2.2 递归写法理解调用栈如果你已经能一遍写对迭代版可以再试试递归版。递归的思路是把“当前位的计算结果”和“剩余链表的递归处理”分开天然处理了进位。class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry: int 0) - Optional[ListNode]: if not l1 and not l2 and not carry: return None total carry if l1: total l1.val l1 l1.next if l2: total l2.val l2 l2.next node ListNode(total % 10) node.next self.addTwoNumbers(l1, l2, total // 10) return node递归版看起来更短但有两个代价。一是每次递归都压栈Python默认递归深度大约1000虽然LeetCode的链表长度不会触发这个限制但如果你拿它跑超长链表就会栈溢出。二是递归难以做到原地修改链表空间复杂度固定是 O(max(m,n))因为每层都新建了一个节点。所以我的建议是迭代版必须写熟递归版作为理解工具。面试时优先写迭代如果面试官追问有没有别的方式再讲递归思路也不迟。2.3 Python实现心得Python写链表题最常遇到的报错是AttributeError: NoneType object has no attribute val。这个错99%是因为在节点为空时访问了l1.val。解决办法很简单每次访问前先判断if l1。另外两个小技巧用Optional[ListNode]做类型注解在 VS Code 里写题会有自动补全和类型提示能少犯低级错误。取个位和进位用total % 10和total // 10比total - 10这种硬编码更通用。因为加法中两位数字和进位加起来最大是 99119所以其实用if total 10也可以但取模写法能直接迁移到“K个链表相加”的变体题里。3. C语言实现指针与内存操作的硬核版3.1 先想清楚三个问题Python里你只管 new 一个对象C语言里你得自己 malloc自己管指针自己小心内存泄漏。写C版之前先回答三个问题结果链表的头节点怎么处理malloc 出来的节点什么时候释放循环结束后如果还有进位怎么追加第一个问题用哨兵节点解决。C语言里你可以在栈上定义一个struct ListNode dummy让cur指向它的next字段返回时返回dummy.next。这样就不用先 malloc 一个头结点再在最后 free 它省掉一段麻烦代码。第二个问题LeetCode的判题环境不检查你手动 malloc 的内存是否释放所以很多人提交完就不管了。但如果你自己在本地写测试程序或者面试官追问你必须能说出如何遍历结果链表并 free 每个节点。第三个问题就是循环条件里要带 carry。C语言没有None空指针就是NULL判断条件写while (l1 || l2 || carry)和Python思路一模一样。3.2 完整可提交的C代码struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { struct ListNode dummy; dummy.next NULL; struct 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; } struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val sum % 10; node-next NULL; cur-next node; cur node; carry sum / 10; } return dummy.next; }这段代码有几个细节要强调dummy是局部变量存在栈上它的生命周期到函数结束为止。返回dummy.next时返回的是堆上 malloc 出来的节点指针不依赖 dummy 本身所以没问题。node-val sum % 10和node-next NULL必须都赋值否则node-next可能是个野指针。sum / 10在非负数场景下没问题。C语言整数除法是向零截断和Python的向下取整不同但本题所有数字都是非负整数所以行为一致。3.3 C语言指针和内存的关键细节C语言的坑主要不在算法而在内存操作。你很容易写出逻辑正确但内存有问题的代码。最容易犯的错误是cur-next node; cur cur-next;写反。这两行顺序不能错先连接再移动。如果先cur node再cur-next node等于把自己指向的节点的 next 指向了自己链表就断了。内存方面我建议在本地调试时写个辅助函数void freeList(struct ListNode* head) { struct ListNode* tmp; while (head) { tmp head; head head-next; free(tmp); } }测试完调用freeList(result)再用 Valgrind 跑一遍确保没有内存泄漏。虽然 LeetCode 不查但这能帮你建立良好的 C 语言编码习惯。面试考 C 的岗位这题就是天然的“指针 内存管理”测试题能一口气写对的人不多。还有一点不要忘记引入#include stdlib.h很多在线编辑器默认已经帮你引入了但本地编译不写就会报malloc未声明别在这种地方浪费排查时间。4. Java实现面向对象与空对象思想4.1 标准迭代解法Java 写法的骨架和 Python 几乎一样区别在于语法的强类型和空指针判断。我直接贴代码class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode cur dummy; int carry 0; while (l1 ! null || l2 ! null || carry ! 0) { int sum carry; if (l1 ! null) { sum l1.val; l1 l1.next; } if (l2 ! null) { sum l2.val; l2 l2.next; } cur.next new ListNode(sum % 10); cur cur.next; carry sum / 10; } return dummy.next; } }Java 里的dummy用new ListNode(0)创建必须给个初始值因为没有类似 Python 的默认构造方式。链表的next默认是null所以不需要像 C 那样手动把node-next置空。很多人在 Java 版容易漏写carry ! 0条件。漏掉之后类似 991 的用例就会少最后一个节点。因为循环体里如果两个链表都为空、carry 为1循环直接退出最后一位进位丢了。4.2 三种语言放在一起的差异把三种语言对照着看比单独刷一遍更有收获。维度PythonC语言Java节点定义class initstructclass 构造器头节点方案ListNode() 或 ListNode(0)栈上 struct dummynew ListNode(0)判空写法if l1:if (l1)if (l1 ! null)取模%%%内存管理自动GCmalloc/free自动GC可出错的点NoneType野指针/内存泄漏NullPointerException对我个人来说用 Python 刷题是最快的因为语法干扰最小用 C 刷能逼自己搞清楚指针指向用 Java 刷则能训练对象引用思维。LeetCode 热门 100 题里很多题都值得用这三种语言各写一遍两数相加尤其适合当第一个试验对象。Java 还有一个隐藏考点dummy和cur指向同一个对象然后cur.next被赋值此时 dummy 的链也同步变长。这涉及对象引用的共享机制理解这一点你就不会在返回时写错成return cur。我见过太多人代码逻辑全对最后还是返回了头节点丢失的空链表。5. 边界条件与扩展思路5.1 题目为什么要逆序存储这不是随意的设计而是为了让你能从头开始逐位相加。如果链表是正序存储比如数字 342 存成 [3,4,2]那么链表头是最高位你做加法得先从链表尾部开始相当于要先反转链表或者用栈把节点倒过来处理起来复杂不少。逆序存储省掉了这一步链表头就是最低位。你只需要同时遍历两条链表就能像列竖式一样从个位开始加。这也是为什么这道题被排在热题前几道它想让你先体会“数据结构如何为算法服务”这件事。理解了这一点你再去做变体题就顺手了。比如“两数相加 II”那道题链表是正序存储的主流解法就是先反转两个链表或者用栈。说白了就是把这道题的思路套回去。5.2 能不能不新建链表直接在原链表上改可以而且这是一个很好的空间优化方案。思路是找出较长的链表把较短的链表对应节点的值加到长链表上长链表最后返回。如果最后还有进位再在尾部追加一个节点。我按这个思路写过一版 Pythonclass Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode: # 先计算两个链表长度 len1, len2 0, 0 p l1 while p: len1 1 p p.next p l2 while p: len2 1 p p.next long_head, short_head (l1, l2) if len1 len2 else (l2, l1) cur_long, cur_short long_head, short_head carry 0 prev None while cur_short: total cur_long.val cur_short.val carry cur_long.val total % 10 carry total // 10 prev cur_long cur_long cur_long.next cur_short cur_short.next while cur_long: total cur_long.val carry cur_long.val total % 10 carry total // 10 prev cur_long cur_long cur_long.next if carry: prev.next ListNode(carry) return long_head这个版本的时间复杂度是 O(mn)空间复杂度降到了 O(1)适合在面试中提出。但我不会把它作为首选提交答案原因有两个它修改了传入的原链表如果面试官要求“不能修改输入链表”直接扣分。代码里要维护prev指针逻辑比新建链表复杂面试手写出 bug 的概率更高。我的建议是先把新建链表的版本写熟再主动提一句“如果允许修改原链表我可以做到 O(1) 空间”然后看面试官反应决定要不要展开。这比上来就写一个复杂版本稳得多。5.3 数字很大、链表很长怎么办两个链表长度最大可以到100。这意味着相加结果最大是 101 位数字远超常规整数类型。这也是为什么题目必须用链表它要考察的不是“能不能用 int 接收”而是“能不能脱离整数类型用模拟方式完成加法”。我见过有人先把链表转换成整数加完再转回链表。这种解法在 LeetCode 里最常见因为测试用例的数字没那么大int 不一定溢出。但要明白这只是取巧一旦测试数据长度接近100用int直接溢出变成负数结果全错用long也救不回来。真正稳的解法就是一位一位模拟。6. 常见报错与调试实录6.1 高频报错速查表语言报错信息常见原因解决办法PythonAttributeError: NoneType object has no attribute val链表节点为空时仍在取val先if l1判空再访问PythonRecursionError: maximum recursion depth exceeded递归解法处理超长链表改用迭代CSegmentation fault空指针解引用、野指针检查指针是否为 NULL、malloc后初始化Cdouble free or corruption重复释放内存释放后把指针置 NULLJavaNullPointerException未判空直接访问.next访问前if (l1 ! null)Java返回结果只有最后一个节点返回了cur而不是dummy.next记住dummy保存头指针6.2 我踩过的隐藏坑第一个隐藏坑循环条件只写了while l1 or l2忘了带carry。当时的用例是[9,9]加[1]本地打印结果只有[0,0]后补了一位才意识到问题。解决方法是把 carry 写进循环条件这一步能统一处理“最后进位”。第二个隐藏坑用dummy之后返回时写错了对象。Python 版容易写成return curJava 版容易写成return cur。cur在循环结束后指向的是结果链表的尾节点返回它只会得到一个节点。一定要返回dummy.next因为dummy的 next 才是真正的头节点。第三个隐藏坑C 语言里 malloc 节点后忘了给node-next NULL。当时是本地跑测试时用 freeList 遍历结果链表尾部连着一个随机地址遍历直接 Segmentation Fault。从那以后我每次 malloc 节点都会顺手初始化next哪怕马上就会被赋值。第四个坑比较隐蔽两个链表都是[0]时结果应该是[0]而不是null或空链表。循环条件里while l1 or l2 or carry进来一次后 l1、l2 都变成空carry 为0循环退出返回dummy.next恰好是一个值为0的节点。但如果你的循环条件是while l1 and l2这个用例直接返回空链表必错。零值用例是我建议每个版本的代码都必须手测的第一条。6.3 一套自测用例模板我在本地刷题时会准备这么一组用例几乎覆盖所有边界用例输入 l1输入 l2期望输出常规加法[2,4,3][5,6,4][7,0,8]零值[0][0][0]长度不等[9,9][1][0,0,1]长度差大[1,8][0][1,8]连续进位[9,9,9,9,9,9,9][9,9,9,9][8,9,9,9,0,0,0,1]写测试的时候Python 可以用list构建链表然后写一个list_to_linkedlist辅助函数C 和 Java 同理。LeetCode 不会帮你输出每一步中间结果所以本地打印每个节点的val比盲调高效得多。6.4 实测下来三种语言的一点感受我用同样一组用例跑了几次Python 版本大概用时几十毫秒Java 版本在几毫秒量级C 版本基本是 0 毫秒。但这道题真正的开销不在语言而在数据结构操作。时间复杂度和空间复杂度三种写法都是 O(max(m,n))新建链表版的空间也是 O(max(m,n))。C 的编译型特性让它的执行时间最短但开发成本最高一段代码里有一半时间在跟指针和内存搏斗。Java 编译成字节码后启动略慢但 LeetCode 统计的是运行时间仍然比 Python 快很多。Python 虽然慢但写起来最接近伪代码适合第一遍理思路。我个人刷题的顺序是先用 Python 把思路验证对再写 Java 版最后挑战 C 版。三道都跑通之后这道题的边界、进位、指针问题基本就刻进肌肉记忆了。最后再分享一个实用小技巧。面试时如果时间紧张别急着写代码先在白板上列三个用例普通用例、长度不等用例、最后有进位的用例。然后边写代码边对照这三个用例检查基本能避开90%的常见错误。这个习惯是我被[9,9] [1]坑过两次之后养成的实测下来比任何方法都好使。