刷 LeetCode 热题100的时候大部分人会自然而然地把“两数相加”排到前面。这个题编号第2题名字听着朴实但它其实是少有的可以用 Python、C语言、JAVA语言分别写一遍并且三种写法差异能让你对链表理解上几个台阶的题目。题目本身不长两个非空链表分别表示两个非负整数数字按逆序存储每个节点只存一位把它们相加后返回同样形式的链表。但就是这道看起来“人畜无害”的题在面试手写、笔试AC、项目复盘的不同场景下藏着一堆关于空指针、进位、内存释放和语言特性的坑。这篇文章会把三种语言的完整解法和踩坑记录都展开讲清楚适合刚开始刷链表题的新手也适合准备面试想对比多语言差异的开发者。1. 题目拆解两数相加到底在考什么1.1 题干信息与隐藏条件先看一个标准示例l1 2 - 4 - 3l2 5 - 6 - 4返回7 - 0 - 8。因为链表是逆序存数字的所以2 - 4 - 3实际代表3425 - 6 - 4代表465两者之和是807按逆序输出7 - 0 - 8。这里最容易被忽略的是“逆序”两个字。逆序存储意味着链表头是各位头节点就是数字的个位下一个节点是十位依次往上。这样做的好处非常明显我们做加法时习惯从个位开始而链表从头部开始遍历正好就是低位到高位进位可以直接向next方向传递不需要先翻转链表。另一个隐藏条件是“非空链表”题干保证了两个链表不会为空但这不意味着循环里可以随便访问l1.next因为两个链表长度不一定相等。比如l1 9 - 9 - 9l2 1短的链表先走到末尾变成null如果你还在循环里无条件取l1.val立刻就会出问题。所以这个题表面考加法实际考的是“你能否在一个循环里同时控制两个链表的移动、处理一个为空时的取值、并正确传递进位”。1.2 为什么它值得出现在热题100里很多人觉得这题简单但它被放进热门100题是有原因的。第一链表遍历是最高频的基础操作而这个题要求同时遍历两条链表比单链表遍历多了一层“两个指针节奏不一致”的处理。第二进位是模拟竖式加法的核心它天然引出了“最终溢出”的边界也就是两个链表都遍历完了但进位还等于1必须额外申请一个节点存放最高位。第三这道题特别适合考察多语言功底因为Python、C、Java对“空值”“内存”“对象引用”的处理完全不同同一个人用三种语言写这个题写出来的代码风格和需要注意的点完全不一样。我见过不少刷题的人用Python一遍写过去觉得太简单然后换C语言写就卡在malloc和指针上也见过Java选手三分钟Lie下解法但追问一句“为什么用dummy node”就答不太上来。所以这道题的价值不在于算法本身而在于它能否暴露出你对语言底层机制的敏感度。接下来先从核心思路讲起。2. 核心思路把竖式加法翻译成循环2.1 为什么不建议先转成整数再加直觉解法是遍历链表把所有数字拼成一个整数相加后再拆成节点。这个方法在Python里看起来能跑因为Python的整数没有位数上限。但在C语言和Java里整数类型是有上限的long大约只能存到19位十进制数链表长度超过19位就会溢出而LeetCode的测试用例里节点数可以到100甚至1000这个方案从根上就是错的。就算Python能容纳大整数转换也需要先遍历一遍链表计算数值相加后又要一遍遍取模构造新链表时间开销并不比逐位相加低而且完全丧失了链表操作的训练意义。所以标准解法就是模拟手算竖式从两个链表的头部开始逐位相加每一位的和对10取余作为结果节点值商作为进位带到下一位。这个过程用while循环实现循环条件不能只写while (l1 ! null l2 ! null)因为两条链表长度可能不同短的遍历完后长的那条还有若干位同时循环结束后还可能有最高位的进位。正确的循环条件应该是l1 ! null || l2 ! null || carry 0。这个条件把“长链表剩余部分”和“最终进位”一起包进去是最不容易漏情况的写法。2.2 一个通用的竖式加法框架不管用什么语言逻辑骨架是一样的。要先构造一个哑节点dummy作为结果链表的头前一个节点然后让当前指针cur从dummy开始。每轮迭代做四件事取两个链表当前节点的值如果某个链表已经为空取值0。计算sum v1 v2 carry。创建新节点节点值等于sum % 10更新carry sum / 10。将cur的下一个指针指向新节点移动cur同时如果原链表不为空则向后移动原链表指针。为什么要用哑节点因为从头创建链表时第一个节点之前没有前驱如果不加哑节点就需要单独判断“这是不是第一个节点”代码会多出一堆if。有了哑节点所有新节点都统一挂到cur.next上最后直接返回dummy.next就是结果链表的头。哑节点在链表题里是极其常见的技巧不只是这一题适用后面做“合并有序链表”“删除倒数第N个节点”都可以复用。有一部分人会想到用递归做这个题递归确实能写但要注意递归深度等于链表长度链表很长时可能栈溢出而且递归代码里需要额外维护进位和节点构造顺序不如迭代直观。我建议面试时优先说迭代法如果面试官追问再提递归解法。3. Python实现短得像是伪代码但陷阱也不少3.1 Python核心代码与逐行解读Python版本可能是三种语言里最容易写的但依然有几个细节值得注意。先放完整解法class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def addTwoNumbers(l1: ListNode, l2: ListNode) - ListNode: dummy ListNode() cur dummy carry 0 while l1 or l2 or carry: v1 l1.val if l1 else 0 v2 l2.val if l2 else 0 total v1 v2 carry carry total // 10 cur.next ListNode(total % 10) cur cur.next if l1: l1 l1.next if l2: l2 l2.next return dummy.next这里最关键的一行是v1 l1.val if l1 else 0。Python里判断一个对象为真本质上调用bool()只要l1不是None条件就为真。所以这个写法等价于l1 is not None时取l1.val否则取0。不建议写成l1.val or 0因为如果节点的值恰好是0l1.val会被当成False结果就错误地用0替代了原来的0虽然数值碰巧一致但这个写法在逻辑上是错的会误导阅读者。while l1 or l2 or carry这个条件也很妙。它把链表遍历结束和进位未清零两种情况统一处理。比如两个链表都遍历完但carry是1循环还会继续进入一轮此时v1和v2都是0total 1创建一个值为1的节点最后carry变成0循环退出。这一下就把“最高位进位”处理掉了不用在循环外面再补一个if。3.2 Python容易踩的隐蔽坑第一个坑是循环里漏写cur cur.next或者漏更新l1 l1.next导致死循环或者结果链表全部串在同一节点上。这种错误在LeetCode本地运行时表现就是超时但在面试白板上非常容易犯强烈建议每次写完循环体反向检查一遍所有移动的指针是否都移动了。第二个坑是返回值写错。有人最后写成return cur结果返回的是链表尾节点只会有最后一个数字。这里cur始终指向当前已构建的最后一个节点而dummy.next才是整个结果链表的头。哑节点存在的意义就是让你能轻松找到头节点千万不要把引用搞混。第三个坑是修改输入链表。如果直接使用l1 l1.next遍历这只是把局部变量指向下一个节点并没有修改输入链表本身。但有些人会顺手写l1.next something来节省节点这样会破坏原始链表。虽然LeetCode判题器不会检查原链表是否被破坏但工程习惯不好而且万一题目后面要求“不能修改原链表”这种写法就直接覆写正确答案了。这个题不靠修改输入来优化空间老老实实新建节点就好。4. C语言实现指针和内存才是真正的考点4.1 C语言核心代码与注意事项C语言没有对象没有自动内存管理所以要把同样的逻辑翻译成结构体指针操作。LeetCode一般会给出结构体定义struct ListNode { int val; struct ListNode *next; };我的实现如下struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { struct ListNode dummy; struct ListNode* cur dummy; struct ListNode* node; int carry 0; int v1, v2, sum; dummy.next NULL; while (l1 || l2 || carry) { v1 l1 ? l1-val : 0; v2 l2 ? l2-val : 0; sum v1 v2 carry; carry sum / 10; node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val sum % 10; node-next NULL; cur-next node; cur node; if (l1) l1 l1-next; if (l2) l2 l2-next; } return dummy.next; }这里我用的是栈上的struct ListNode dummy作为哑节点而不是malloc。原因后面会详细说。注意循环体内每创建一个新节点必须把node-next置为NULL否则新节点的next是一个随机地址最后返回的结果链表尾部就会指向垃圾内存本地调用时遍历到末尾就会段错误。LeetCode内部判题和打印结果时也会遍历链表遇到乱指针就直接报runtime error。4.2 内存管理的三个关键细节C语言版第一个关键点是哑节点的创建方式。很多教程会写struct ListNode* dummy malloc(sizeof(struct ListNode));然后在结尾return dummy-next;。这个写法没有错但会让哑节点本身变成一块“孤儿内存”——它不在结果链表里调用者拿到返回的头指针后无法访问到dummy指针来释放它所以代码存在内存泄漏。LeetCode不检测内存泄漏所以能通过但如果在本地用Valgrind检查就会报告一块内存泄漏。因此我更推荐在栈上声明一个dummy结构体变量让cur指向它的地址函数返回时哑节点作为栈变量自动释放不需要手动管理同时结果链表已经挂在dummy.next上完全不受影响。这是一个面试时很加分的细节。第二个关键点是malloc失败检查。严谨的工程代码应该判断node NULL时怎么处理但刷题场景里一般不会遇到写了反而显得啰嗦。如果要在本地做健壮性验证可以在malloc后加一句if (node NULL) return NULL;面试时提一句“这里理论上要检查malloc返回值”就够了。第三个关键点是标准C没有bool类型所以while (l1 || l2 || carry)里整型carry的0和非0就可以作为循环条件。如果你写了#include stdbool.h然后用bool carry false;也没问题但完全没有必要。C语言里l1本身是指针指针的直接判断等价于l1 ! NULL代码能短则短读起来反而更快。4.3 长度不一致与最终进位的C语言处理C语言的指针操作很容易让人在“长度不一致”这里翻车。如果写下while (l1 l2)那么一旦某个链表先走到NULL循环就结束剩下的链表高位没有被加进去直接丢掉。比如[9,9]加[1]答案是[0,0,1]但错误循环只算到第二位的90110然后把carry丢了返回[0,1]完全不对。正确写法必须用||把所有未完成条件合并并且在循环体内部用三目运算符处理空指针。三目运算符也有一点需要注意v1 l1 ? l1-val : 0;其实可以拆成int v1 l1 NULL ? 0 : l1-val;两种写法含义一样。新手容易写的错误版本是v1 l1-val ? l1-val : 0;这个只有在val为0时会取0但不巧的是0本身就是要表示的数字所以能通过一些测试但遇到非0值也没问题如果val是0它的条件为假得到0碰巧正确如果val非0条件为真得到val也正确。看起来对但这是“碰巧正确”它把“节点指针是否为空”和“节点值是否非零”混为一谈。只要val为0逻辑就走错了分支只不过数值还是0。这种代码会让读代码的人崩溃面试官也会皱眉头。正确的判断对象一定是指针不是值。5. Java实现面向对象的“引用版”链表达5.1 Java核心代码与逐段拆解Java的链表节点是一个类持有当前值和指向下一个节点的引用。LeetCode环境里的ListNode通常长这样public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }解法代码如下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 v1 (l1 ! null) ? l1.val : 0; int v2 (l2 ! null) ? l2.val : 0; int sum v1 v2 carry; carry sum / 10; cur.next new ListNode(sum % 10); cur cur.next; if (l1 ! null) l1 l1.next; if (l2 ! null) l2 l2.next; } return dummy.next; } }Java版和Python版结构几乎一样差别主要在空值判断的方式。Java没有Python那种“if l1”的隐式布尔转换写if里必须是布尔表达式所以老老实实写l1 ! null。三元运算符(l1 ! null) ? l1.val : 0是处理空指针的标准姿势。注意三元运算符的优先级和结合性整个表达式作为赋值右值先计算条件然后只执行选中的分支。所以不会在l1 null时访问l1.val这一点很关键。5.2 Java与Python/C的差异点Java的“引用”对很多从C转过来的人来说是一个奇妙的中间态。它不像C语言那样需要手动管理内存也不像Python那样变量名完全动态。ListNode dummy new ListNode(0);在堆上创建了一个对象变量dummy持有它的引用。ListNode cur dummy;让cur和dummy指向同一个对象。之后cur.next怎么改dummy.next也会同步看到因为它们是同一个对象。这个概念是理解这个解法的核心如果不懂引用和对象的区别很容易觉得“cur指向dummy然后cur变了dummy应该不变啊”从而画错链表图。Java里还要注意一个坑new ListNode(0)构造器是必须存在的。LeetCode的ListNode类通常有带int val的构造器所以可以直接用。如果你在本地自己定义类时写了ListNode()无参构造器并且val没有初始化默认是0也可以。但建议显式传入0一方面语义清楚另一方面避免某些在线编辑器模板没有无参构造器导致编译失败。另外一个区别是整数计算。Java的sum / 10对于正整数而言就是整除sum % 10取余。这里没有负数情况所以放心用。如果担心面试官考负数题目明确说“非负整数”所以不需要考虑。还有一些人会把carry sum / 10;写成carry (sum - sum % 10) / 10;这是完全没有必要的绕路。直接整除最清晰。5.3 Java的空指针排查习惯Java最容易翻车的地方是空指针异常。错误示范是把循环体内部取值写成int v1 l1 null ? 0 : l1.val; int v2 l2 null ? 0 : l2.val;这是对的。但如果把条件反过来写成l1.val ! null就是拿基本类型int和null比较编译都过不了。另一个常见错误是在循环外先判断“如果l1走到末尾”然后再在循环里无条件l1 l1.next导致短链表到末尾后下一次循环访问前没有判空。这也是为什么推荐在循环体内统一用三元表达式取值、统一移动指针而不是把“取当前值”和“移动指针”拆成两个复杂的if分支。Java的JVM自带垃圾回收所以不用手动释放dummy节点也不用担心内存泄漏。但在内存分析时要知道dummy节点一直通过cur.next被原dummy引用实际上dummy.next指向结果链表的第一个节点所以整个结果链表都能从dummy出发访问到当方法返回时局部变量dummy消失但返回给调用者的dummy.next引用才是根。如果调用者只保存了返回的头节点那个头节点不是哑节点哑节点本身没有被任何全局引用持有会被GC回收。不会出现C语言那样的泄漏。Java笔试时不用关心这些但如果面试官追问说清楚引用生命周期会很加分。6. 复杂度分析与边界用例6.1 时间复杂度和空间复杂度假设l1长度为ml2长度为n这个算法会遍历两个链表各一次结果链表的长度最多是max(m, n) 1所以时间复杂度是O(max(m, n))。空间方面我们创建了一个新链表节点数同样是O(max(m, n))额外使用常量级别的carry和几个指针所以空间复杂度也是O(max(m, n))这个“额外”指的是除了输入之外新增的节点。如果把创建结果链表视为必要输出一般也这么说。有人会问能不能在l1上原地修改节省空间。理论上可以先确定长链表复用它的节点在长链表上更新val短链表走完后就只遍历长链表最终如果还有进位就追加节点。但这会修改输入链表工程上是个坏味道而且实现时要分“哪个链表长”的预处理代码复杂度和出错概率都会上升。LeetCode不会因为空间复杂度O(1)给你加分所以标准解法用新链表最稳妥。6.2 一组值得跑一遍的边界用例把测试用例整理成表格方便自测输入l1输入l2期望输出说明[2,4,3][5,6,4][7,0,8]官方示例[0][0][0]都是零不会出现空结果[9,9][1][0,0,1]长度不同且产生进位[9,9,9][1][0,0,0,1]连续进位到最高位[5][5][0,1]个位为0产生最高位1长度1000长度999长度1000或1001验证长链表的非溢出处理第3个用例最容易暴露循环条件错误。用while(l1 l2)的写法会漏掉第一个链表的最后一个9得到[0,1]而不是[0,0,1]。第4个用例专门测试“最终进位”两个链表都遍历完时carry还是1必须再创建一个节点。第5个用例测试“节点值为0”时是否正确处理也能排除掉l1.val or 0这种错误写法。在本地跑自测时可以额外验证一件事输入链表有没有被意外修改。如果你用Python写遍历完l1后再重新遍历print一下如果l1的最后一个节点变成了人为构造的新节点那说明代码里误用了l1.next something要立即改掉。C语言则不需要太关心因为手动改next很容易导致内存问题。7. 三种语言实战踩坑记录与排查方法7.1 PythonAttributeError: ‘NoneType’ object has no attribute ‘val’这是Python版最常见的报错。场景是这样的你写了while l1 and l2作为循环条件循环结束后以为已经处理完了但实际上如果l1比l2长后面的l1还有节点没参与运算或者你在循环体内部无条件写v1 l1.val当某个链表先走到None时下一轮就崩了。报错信息会明确告诉你哪个对象是NoneType但不会告诉你是因为循环条件写错了还是取值没判空。排查方法是先看while条件。正确的条件必须是while l1 or l2 or carry而循环体里取值必须用l1.val if l1 else 0。如果两处都正确就不可能出现NoneType错误。还有一个隐蔽点cur.next应该指向ListNode(total % 10)如果你不小心写成cur.next cur会导致循环链表Python在输出时会死循环LeetCode表现为超时而不是直接崩溃。这种错误需要靠打印每个节点地址去定位。7.2 C语言Segmentation fault 到底是谁的锅C语言版的大部分崩溃都可以归到三件事上。第一件事是没有初始化node-next。如果你在创建新节点后忘记写node-next NULL;那么cur-next node;之后结果链表最后一个节点的next是随机值。LeetCode遍历完结果时会顺藤摸瓜访问一个非法地址立刻段错误。这种崩溃有个特点小用例可能不崩因为随机值恰好是0或者低地址但链表稍长或者内存布局变化时就崩非常难复现。解决办法很简单创建节点时立刻置NULL。第二件事是循环条件错误导致空指针解引用。例如while (l1 l2)的写法下如果l1走到NULL但l2还有节点循环退出后续没有处理剩余节点虽然不会段错误但结果错误。如果继续在循环外访问l1-val就会崩。正确做法是把取值判空内聚到循环体中。第三件事是误释放了dummy节点。如果你用了堆上malloc的dummy然后想在返回前free(dummy)这会导致返回的dummy-next变成一个悬空指针调用者访问头节点时就段错误。记住哑节点不能free因为返回链表后外部没有哑节点的指针无法安全释放所以不如用栈变量dummy。我用栈上dummy以来再没遇到过这个坑。排查段错误时先注释掉malloc相关的优化加打印。比如在循环开头printf计算l1/l2的地址看第几次迭代崩溃。也可以把node-next NULL;放在malloc后立刻执行基本能排除一类问题。7.3 JavaNullPointerException 的经典来源Java的空指针报错信息通常会给到具体行号相对友好。最常见的来源是取值时把判断条件写反了比如int v1 l1 null ? 0 : l1.val;这是对的。如果写成l1 null ? l1.val : 0当l1为null时三元运算符会执行l1.valNPE立刻出现。因为三元运算符会评估被选中的表达式而不是两个分支都评估。所以写三元表达式时先写条件再写“条件为真时”的结果最后写“条件为假时”的结果顺序别搞混。另一个典型NPE出现在移动链表指针时。如果你在循环体里只移动了一次指针比如只写了l1 l1.next;而忘了l2 l2.next;会导致l2一直指向同一个节点循环陷入死循环最后可能因为list太大而内存溢出。虽然不叫NullPointerException但也是不仔细的后果。排查这种问题最快的办法是在循环里打印l1和l2当前的val别用System.out.println去刷屏可以用条件打印机。LeetCode上不允许打印太多输出本地调试没问题。7.4 一套可复用的自测脚手架无论用哪种语言我都建议准备一套“数组转链表、链表打印、用例驱动”的小工具。以Python为例本地自测可以通过以下辅助函数快速构造用例def build_linked_list(nums): dummy ListNode() cur dummy for val in nums: cur.next ListNode(val) cur cur.next return dummy.next def print_linked_list(head): values [] while head: values.append(head.val) head head.next print(values)测试时写这样几行l1 build_linked_list([9, 9, 9]) l2 build_linked_list([1]) result addTwoNumbers(l1, l2) print_linked_list(result) # 期望 [0, 0, 0, 1]还可以写一个简单断言函数把表格里所有用例都跑一遍确保最终结果列表和期望列表相等。C语言和Java也可以套用同样的思路只是构造数组和打印稍麻烦一点。但正是这样一个脚手架能让你在本地快速重现LeetCode上的错误而不是毫无头绪地盯着红色Runtime Error发呆。我强烈建议把这几段工具代码存成自己的刷题模板遇到链表题直接复用。8. 我在三种语言切换中摸出的几条经验这个题我用三种语言各写过不下五遍每次写都有新感受。最开始是Python一遍过觉得简单后来用C语言写被malloc和哑节点搞到头大再后来用Java写开始意识到引用和对象的区别。这里分享几条我在实际手写中总结出的经验。第一条写代码之前先画图。画两个链表把他们像竖式一样上下对齐用一个小箭头表示carry。这个题难的从来不是逻辑而是指针和空值的边界画图能让你在写while条件时不容易漏。面试的时候动手写代码前花三十秒画图面试官通常会认为你思路清晰。第二条返回值一定是哑节点的next不是当前指针。当前指针会随着循环走到最后一个节点它只是“最后一个已经构造的节点”而哑节点的next才是整个结果链表的头。这个错误Python和Java都很常见我甚至见过有经验的人在不经意间也会写错。第三条如果时间允许三种语言都写一遍。这个题是少有的“用不同语言写复杂度完全不同”的题。Python让你练条件表达式的简洁C让你被迫关注内存的来龙去脉Java让你理解对象引用。很多人在力扣上只追求AC其实用两种语言各写一遍比反复刷十道简单题更有收获。我个人实测下来先写C再写Java最后用Python优化表达式整个人的指针观都会清晰很多。最后再分享一个小技巧这个题的循环条件while (l1 || l2 || carry)可以背下来因为很多“链表逐位操作”的题都能套用比如“字符串相加”“二进制链表转整数”的类似变体。遇到新题时只要把val的取值改成“当前字符减‘0’”把结果节点改成字符串追加核心框架完全不动。把一道热题吃透远比刷十道同质题有价值。希望这篇复盘能帮你把两数相加这个“入门题”彻底变成自己的“送分题”。