企业官网建设流程全解析

1. 先聊题目：为什么这道题能进LeetCode前100

LeetCode第2题“两数相加”算是链表入门的基础题了，正好在LeetCode热门100题榜单里。很多刷题党把它当成“链表第一题”来做，因为它不像反转链表那样纯考指针操作，也不像合并有序链表那样有明确的分治背景，它把数学加法中“逐位相加、逢十进一”的过程，原封不动地搬到了链表上。

我第一次刷这道题时，其实是先栽了跟头的。当时习惯用数组思维，想着把两个链表的数字先取出来转成整型，相加完了再转回链表，代码写到一半发现样例测试没问题，一交就开始报错。再看一眼题目描述，里面有一行小字：链表长度可能超过64位整数的表示范围。也就是说，这条路在工程上根本走不通。后来才明白这道题的真实考点是“手写竖式加法”，不是“让你调BigInteger库”。

先说清楚这道题适合谁：正在看链表基础的人、准备面试需要练手写数据结构的人、想搞明白递归和迭代边界怎么处理的人，都值得把它吃透。它本身不复杂，但里面包含的链表遍历、进位维护、哨兵节点使用、边界条件收尾，都是后续做中等难度链表题（比如两数相加II、合并K个升序链表）直接要用的底层能力。

顺便提一句，LeetCode周赛430我刚打完，里面也有一道和“按位处理+进位”思路非常像的题。那些题表面是硬模拟，底层全是这道题的变形。

2. 题目本质：逆序存储反而帮了大忙

2.1 输入格式到底在表达什么

题目给的链表头节点是数字的最低位，也就是说链表是逆序存数的。比如数字342，在链表里是 2 -> 4 -> 3，头节点存个位。

这个设定刚看会觉得别扭，因为平时写数字都是从高位往低位读。但换成竖式加法想想就顺了：我们小学列竖式算加法，是不是从个位开始一位一位往左加？链表头节点存个位，正好让我们从头节点开始逐位相加时，天然就是“从低位往高位”推进，完全不需要先反转链表。

遇到一个数据结构设计，先别急着否定它，想想它在为什么场景服务。逆序链表这个设计，是专门为“加法进位从左往右传递”服务的。

2.2 为什么数组/整数转换方案必然炸掉

很多人第一反应是遍历两个链表，把数字拼出来再相加，最后转回链表。这个思路在数字很小的时候确实能过，但题目里明确说了链表长度可以很长，长度超过64位甚至更长时：

• 64位整数撑不住超大数，换算成字符串做加法又回到了手写竖式的老路；
• 就算语言支持大数（比如Python的int），面试官也不会满意，因为这不是考你语言特性，是考链表操作能力；
• 转换过程本身要遍历两遍、构建一遍，时间空间都亏。

所以这道题的标准解法，就是模拟竖式加法：同时遍历两个链表，每轮取两个节点的值，加上上一位的进位，算出当前位的值和下一位的进位，生成新节点挂到结果链表上。

2.3 核心状态其实只有两个

梳理一下整个过程，每一轮迭代的核心就两件事：

1. 当前位的数字是多少；
2. 要不要往下一个节点进位。

当前位数字等于 (p.val + q.val + carry) 对10取余，进位值等于 (p.val + q.val + carry) 除以10取整。这里的carry只能是0或1，因为两个一位数相加最高不会超过9+9+1=19，所以进位最多是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, val=0, next=None): # 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.next

Python的写法有个细节：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 递归的拆法

迭代是“从低位到高位不断生成节点”，递归则是把“当前位的加法”和“剩余节点相加的结果”拆开。每层递归只做一件事：

1. 计算当前位的和与进位；
2. 递归计算剩余部分的和；
3. 把当前位的新节点指向剩余部分的结果。

递归终止条件：两个链表都为空，且进位为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，另一个正常，结果应该直接等于正常链表，当然正常遍历也能出来；
• 全是0：0 和 0，结果 0；
• 大数溢出测试：构造一个30位的链表，验证结果和手写竖式一致。

这些用例覆盖了“有没有进位”“长度相同还是不同”“链表空不空”三种维度。基本逻辑不复杂的题，最大的敌人就是这些细节。

6. 进阶：如果链表是正序存储，还能这么写吗

6.1 正序场景下的新问题

LeetCode里有道姐妹题“两数相加II”，链表是正序存储数字的：342存成3 -> 4 -> 2，头节点是最高位。那题目就没这么幸福了，因为从最高位开始加，如果低位有进位，你是没法提前知道的。

正序链表相加的常规解法有三种：

1. 先反转两个链表，按逆序相加，最后再反转结果；
2. 用两个栈分别存储两个链表的节点，弹出时从低位开始加，结果用头插法构建；
3. 递归处理，先递归到底后再回溯相加，但进位问题需要额外处理。

思路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刷题的价值，从来不在数量，在你能不能把一个通用模式真正吃透。