1. 先聊题目为什么这道题能进LeetCode前100LeetCode第2题“两数相加”算是链表入门的基础题了正好在LeetCode热门100题榜单里。很多刷题党把它当成“链表第一题”来做因为它不像反转链表那样纯考指针操作也不像合并有序链表那样有明确的分治背景它把数学加法中“逐位相加、逢十进一”的过程原封不动地搬到了链表上。我第一次刷这道题时其实是先栽了跟头的。当时习惯用数组思维想着把两个链表的数字先取出来转成整型相加完了再转回链表代码写到一半发现样例测试没问题一交就开始报错。再看一眼题目描述里面有一行小字链表长度可能超过64位整数的表示范围。也就是说这条路在工程上根本走不通。后来才明白这道题的真实考点是“手写竖式加法”不是“让你调BigInteger库”。先说清楚这道题适合谁正在看链表基础的人、准备面试需要练手写数据结构的人、想搞明白递归和迭代边界怎么处理的人都值得把它吃透。它本身不复杂但里面包含的链表遍历、进位维护、哨兵节点使用、边界条件收尾都是后续做中等难度链表题比如两数相加II、合并K个升序链表直接要用的底层能力。顺便提一句LeetCode周赛430我刚打完里面也有一道和“按位处理进位”思路非常像的题。那些题表面是硬模拟底层全是这道题的变形。2. 题目本质逆序存储反而帮了大忙2.1 输入格式到底在表达什么题目给的链表头节点是数字的最低位也就是说链表是逆序存数的。比如数字342在链表里是 2 - 4 - 3头节点存个位。这个设定刚看会觉得别扭因为平时写数字都是从高位往低位读。但换成竖式加法想想就顺了我们小学列竖式算加法是不是从个位开始一位一位往左加链表头节点存个位正好让我们从头节点开始逐位相加时天然就是“从低位往高位”推进完全不需要先反转链表。遇到一个数据结构设计先别急着否定它想想它在为什么场景服务。逆序链表这个设计是专门为“加法进位从左往右传递”服务的。2.2 为什么数组/整数转换方案必然炸掉很多人第一反应是遍历两个链表把数字拼出来再相加最后转回链表。这个思路在数字很小的时候确实能过但题目里明确说了链表长度可以很长长度超过64位甚至更长时64位整数撑不住超大数换算成字符串做加法又回到了手写竖式的老路就算语言支持大数比如Python的int面试官也不会满意因为这不是考你语言特性是考链表操作能力转换过程本身要遍历两遍、构建一遍时间空间都亏。所以这道题的标准解法就是模拟竖式加法同时遍历两个链表每轮取两个节点的值加上上一位的进位算出当前位的值和下一位的进位生成新节点挂到结果链表上。2.3 核心状态其实只有两个梳理一下整个过程每一轮迭代的核心就两件事当前位的数字是多少要不要往下一个节点进位。当前位数字等于 (p.val q.val carry) 对10取余进位值等于 (p.val q.val carry) 除以10取整。这里的carry只能是0或1因为两个一位数相加最高不会超过99119所以进位最多是1。这个“最多进1”的特性让代码判断变得特别简单你甚至不需要考虑carry大于1的复杂情况。3. 迭代解法从第一版到能AC的完整过程3.1 骨架代码怎么搭先定义结果链表的头和尾。用哨兵节点dummy head是最稳妥的做法好处是即使结果链表一个节点都还没有你也能通过 dummy.next 访问到头节点不用为判空逻辑写多余分支。每一轮循环的标准步骤如果p不为空取p.val如果q不为空取q.val算sum pVal qVal carry当前位数字存到新节点挂到结果链表尾部更新carry sum / 10移动p和q到各自的下一个节点如果有。循环结束条件有两个p和q都为空且carry为0。注意是“且”如果p和q遍历完了但carry还是1说明最高位还有一个进位比如 5 5 10结果链表应该多出一个1节点。这是最经典的遗漏点后面我会专门讲。3.2 代码逐行拆解以Java为例我给出一个能直接AC的版本并解释每一段在干嘛/** * Definition for singly-linked list. * 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) { // dummyHead哨兵节点避免结果链表为空时的特殊判断 ListNode dummyHead new ListNode(0); ListNode tail dummyHead; int carry 0; // l1和l2只要有一个没走完就继续循环 while (l1 ! null || l2 ! null) { int x (l1 ! null) ? l1.val : 0; int y (l2 ! null) ? l2.val : 0; int sum x y carry; // 更新进位sum 10 时 carry 1否则 0 carry sum / 10; // 当前位数字sum % 10 tail.next new ListNode(sum % 10); tail tail.next; if (l1 ! null) l1 l1.next; if (l2 ! null) l2 l2.next; } // 最高位如果还有进位需要补一个节点 if (carry 0) { tail.next new ListNode(carry); } return dummyHead.next; } }这段代码的思路非常直接两个链表同时向前推进谁短了谁就补0直到两个都走完最后检查有没有多余进位。你会发现它几乎没有复杂分支原因就是逆序链表让“对齐低位”这件事变成了自然行为。每种语言写起来差不太多Python版本可以这样# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(0) cur dummy carry 0 while l1 or l2 or carry: v1 l1.val if l1 else 0 v2 l2.val if l2 else 0 s v1 v2 carry cur.next ListNode(s % 10) carry s // 10 cur cur.next if l1: l1 l1.next if l2: l2 l2.next return dummy.nextPython的写法有个细节while循环条件是l1 or l2 or carry这样把“最后进位”也合并进了循环代码更简洁。3.3 时间复杂度与空间复杂度时间O(max(m, n))m和n是两个链表的长度。因为每轮循环处理一个节点循环次数等于较长链表的长度加上可能的最后一次进位。空间如果不算输出结果占用的空间额外空间是O(1)只用了几个指针变量。但如果把结果链表本身算进去是O(max(m, n))。面试时被问到复杂度是标准回答主要是O(max(m,n))的时间因为每个节点最多访问一次。空间要看你算不算输出链表通常答“额外空间O(1)”就可以了。4. 递归解法另一种等价的思考方式4.1 递归的拆法迭代是“从低位到高位不断生成节点”递归则是把“当前位的加法”和“剩余节点相加的结果”拆开。每层递归只做一件事计算当前位的和与进位递归计算剩余部分的和把当前位的新节点指向剩余部分的结果。递归终止条件两个链表都为空且进位为0返回null。这里同样要把进位纳入终止条件不然会丢掉最高位的1。4.2 递归代码示例class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return helper(l1, l2, 0); } private ListNode helper(ListNode l1, ListNode l2, int carry) { if (l1 null l2 null carry 0) { return null; } int x (l1 ! null) ? l1.val : 0; int y (l2 ! null) ? l2.val : 0; int sum x y carry; ListNode node new ListNode(sum % 10); // 递归处理剩余部分注意null节点的next也传null ListNode nextL1 (l1 ! null) ? l1.next : null; ListNode nextL2 (l2 ! null) ? l2.next : null; node.next helper(nextL1, nextL2, sum / 10); return node; } }递归版的代码看着更短但有两处容易出错终止条件漏掉carry传下一层递归时忘了先把l1和l2判空再取next。我的建议递归版适合理解思路面试手写推荐迭代版。因为递归如果递归深度很大链表很长会有栈溢出的风险。虽然LeetCode的测试数据不会把你逼到栈溢出但“递归深度等于链表长度”这个事实和迭代O(1)额外栈空间相比是要扣分的点。5. 边界情况与测试用例这里才是真正的分水岭5.1 实际写代码最容易翻车的地方第一个坑是最高位进位丢失。输入 5 - 和 5 -正确输出应该是 0 - 1。如果你最后的if (carry 0)忘了写或者把while循环条件写成了 l1 ! null l2 ! null就会丢掉那个1。很多新手把链表的遍历习惯带进来了习惯性写成“两个链表都非空才循环”结果一个是空一个非空时直接漏掉了剩余部分。正确写法是“只要有一个非空就循环”空缺位补0。第二个坑是两个链表长度不一致时短链表走了就不再动了。常见错误是只移动p不移动q或者移动时没判空。l1或l2可能已经null取val前不判空会直接NullPointerException。第三个坑是链表自带的节点定义别改比如LeetCode的ListNode构造函数有带next和不带next两种用的时候注意别把构造签名写错。有些同学喜欢自己封装一个“创建链表”的工具函数本地测试用着方便提交时别忘了删掉和题目无关的类。5.2 值得测试的用例集合刷题不是提交AC就完事真正吃透一道题建议把这几种用例都跑一遍基本情况2 - 4 - 3 和 5 - 6 - 4结果 7 - 0 - 8长度不一致1 - 8 和 0结果 1 - 8结果变长9 - 9 - 9 和 1结果 0 - 0 - 0 - 1空链表一个链表为null另一个正常结果应该直接等于正常链表当然正常遍历也能出来全是00 和 0结果 0大数溢出测试构造一个30位的链表验证结果和手写竖式一致。这些用例覆盖了“有没有进位”“长度相同还是不同”“链表空不空”三种维度。基本逻辑不复杂的题最大的敌人就是这些细节。6. 进阶如果链表是正序存储还能这么写吗6.1 正序场景下的新问题LeetCode里有道姐妹题“两数相加II”链表是正序存储数字的342存成3 - 4 - 2头节点是最高位。那题目就没这么幸福了因为从最高位开始加如果低位有进位你是没法提前知道的。正序链表相加的常规解法有三种先反转两个链表按逆序相加最后再反转结果用两个栈分别存储两个链表的节点弹出时从低位开始加结果用头插法构建递归处理先递归到底后再回溯相加但进位问题需要额外处理。思路1最容易理解也最好写。思路2避免了反转链条的额外操作逻辑上更直接一点。无论哪种都比原题多了一步“解决顺序问题”的功夫。6.2 从这道题能沉淀出的通用能力“两数相加”这道题最有价值的地方不是让你背下这段代码而是让你理解链表作为“按位处理”载体时的天然优势哨兵节点如何帮你省掉麻烦的判空分支循环条件和边界状态carry要一起参与判断短链表的缺失位用0补齐比写一堆if else更优雅。这些思路在后来的合并两个有序链表、分隔链表、K个一组翻转链表、甚至树相关的递归题里都能复用到。链表题刷多了你会发现所谓的“不同类型的题”底层逻辑其实高度相似都是“游标移动 链接关系维护 边界条件收尾”。7. 测试代码与本地调试技巧7.1 构造链表和打印链表的通用模板LeetCode上你只需要写Solution类不需要处理输入输出。但本地调试时没有main方法很难受。我每次刷链表题都会在本地建一个工具类包含两个方法一个是根据数组生成链表一个是打印链表。public class ListNodeUtil { public static ListNode buildList(int[] arr) { ListNode dummy new ListNode(0); ListNode cur dummy; for (int val : arr) { cur.next new ListNode(val); cur cur.next; } return dummy.next; } public static String printList(ListNode head) { StringBuilder sb new StringBuilder(); while (head ! null) { sb.append(head.val).append( - ); head head.next; } sb.append(null); return sb.toString(); } }有了这两个工具测试用例就写得很舒服public class TestAddTwoNumbers { public static void main(String[] args) { Solution solution new Solution(); ListNode l1 ListNodeUtil.buildList(new int[]{2, 4, 3}); ListNode l2 ListNodeUtil.buildList(new int[]{5, 6, 4}); ListNode result solution.addTwoNumbers(l1, l2); System.out.println(ListNodeUtil.printList(result)); ListNode l3 ListNodeUtil.buildList(new int[]{9, 9, 9}); ListNode l4 ListNodeUtil.buildList(new int[]{1}); ListNode result2 solution.addTwoNumbers(l3, l4); System.out.println(ListNodeUtil.printList(result2)); } }7.2 本地调试时注意LeetCode不背锅的坑有时候在本地跑得好好的一提交就编译错误原因多半是main函数和工具类写在了同一个文件里但LeetCode后台只认Solution类自己定义的ListNode类名和LeetCode内建的类名冲突重复定义了用了题目没引入的包比如Arrays类的import漏了。建议的做法在本地建一个单独的项目把ListNode、Solution、工具类分开文件存。提交时只复制Solution类的内容到LeetCode编辑框就不会出错。8. 我的一点心得这道题我已经刷过不止一遍了。第一遍是用迭代解法AC完就忘第二遍是面试前回炉突然发现自己第一次写的时候居然还在“先转数组再相加”属于典型的思维偷懒。后来把递归版、正序版、甚至用栈实现的版本都写了一遍才真正理解它的内核就是“进位模拟”。刷题这事的规律是一开始觉得每道题都是新题刷到一定量之后会觉得都是老朋友。两数相加这道题可以说是我在链表这块的启蒙题。你把它彻底弄明白之后再去做合并K个升序链表、K个一组翻转链表、重排链表会明显感觉到思想上更顺了。最后分享一个我常用的刷题习惯一道简单题AC之后别急着下一道试着改一改条件再做一遍。比如这道题你可以自己问自己“如果链表是正序呢”“如果要求原地修改不能新建链表呢”“如果数字不是10进制而是2进制呢”这几个变体一练你对这道题的掌握就远不止“做过一遍”了。LeetCode刷题的价值从来不在数量在你能不能把一个通用模式真正吃透。