Vue.js

Appearance

On this page

实战：两数相加 ​

想象一下小学时学的竖式加法：从个位开始，逐位相加，遇到进位就往高位传递。

这道题就是要在链表上模拟这个过程。有趣的是，题目设计成逆序存储——数字的个位在链表头。这样设计有什么好处？它让我们可以从链表头开始处理，正好符合手算加法的顺序！

问题描述 ​

LeetCode 2. Add Two Numbers

给你两个非空的链表，表示两个非负整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

示例：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

问题分析 ​

首先要问一个问题：为什么题目要用逆序存储？

思考一下手算加法的过程：

  • 从个位开始，逐位相加
  • 如果和大于等于 10，产生进位
  • 进位传递给高位

如果数字是正序存储（高位在前），我们需要先遍历到末尾才能开始加法。但逆序存储让个位在链表头，可以从头开始处理，完美匹配加法顺序！

现在问第二个问题：循环什么时候结束？

需要满足三个条件：

  1. l1 遍历完了
  2. l2 遍历完了
  3. 没有进位了

任何一个条件不满足，都要继续处理。

解法：模拟加法 ​

思路非常直接：逐位相加，处理进位，构建结果链表。

javascript
function addTwoNumbers(l1, l2) {
  const dummy = new ListNode(0);  // 哨兵节点
  let curr = dummy;
  let carry = 0;  // 进位
  
  // 只要有任何一个条件满足，就继续
  while (l1 !== null || l2 !== null || carry !== 0) {
    // 取当前位的值（链表为空则用 0）
    const val1 = l1 ? l1.val : 0;
    const val2 = l2 ? l2.val : 0;
    
    // 计算当前位的和
    const sum = val1 + val2 + carry;
    carry = Math.floor(sum / 10);  // 新的进位
    
    // 创建新节点
    curr.next = new ListNode(sum % 10);
    curr = curr.next;
    
    // 移动指针
    if (l1) l1 = l1.next;
    if (l2) l2 = l2.next;
  }
  
  return dummy.next;
}

复杂度分析：

  • 时间：O(max(m, n))，遍历较长的链表
  • 空间：O(max(m, n))，存储结果链表

执行过程可视化 ​

以 l1 = [2,4,3], l2 = [5,6,4] 为例（代表 342 + 465）：

初始：carry = 0

第1轮：处理个位
  val1 = 2, val2 = 5
  sum = 2 + 5 + 0 = 7
  carry = 0, 创建节点 7
  
  l1:  2 → 4 → 3
       ↓
  l2:  5 → 6 → 4
       ↓
  结果: 7

第2轮：处理十位
  val1 = 4, val2 = 6
  sum = 4 + 6 + 0 = 10
  carry = 1, 创建节点 0
  
  结果: 7 → 0

第3轮：处理百位
  val1 = 3, val2 = 4
  sum = 3 + 4 + 1 = 8  // 别忘了进位！
  carry = 0, 创建节点 8
  
  结果: 7 → 0 → 8

l1=null, l2=null, carry=0 → 循环结束

输出：[7, 0, 8]（代表 807）

关键细节 ​

1. 循环条件必须包含 carry ​

javascript
// ❌ 错误：漏了 carry 条件
while (l1 !== null || l2 !== null)

// 问题：输入 [5], [5]
// 5 + 5 = 10，结果应该是 [0, 1]
// 但如果只检查 l1 和 l2，第一轮后都为 null，循环结束
// 输出 [0]，漏掉了最高位的进位！
javascript
// ✅ 正确：三个条件都检查
while (l1 !== null || l2 !== null || carry !== 0)

2. 空链表用 0 代替 ​

当一个链表已经遍历完，但另一个还有节点时，用 0 代替已结束链表的值：

javascript
const val1 = l1 ? l1.val : 0;
const val2 = l2 ? l2.val : 0;

3. 进位计算 ​

javascript
const sum = val1 + val2 + carry;
carry = Math.floor(sum / 10);  // 进位（0 或 1）
const digit = sum % 10;         // 当前位

解法二：递归（优雅版） ​

同样的逻辑也可以用递归实现：

javascript
function addTwoNumbers(l1, l2, carry = 0) {
  // 基准情况：两个链表都空，且无进位
  if (l1 === null && l2 === null && carry === 0) {
    return null;
  }
  
  const val1 = l1 ? l1.val : 0;
  const val2 = l2 ? l2.val : 0;
  const sum = val1 + val2 + carry;
  
  const node = new ListNode(sum % 10);
  node.next = addTwoNumbers(
    l1 ? l1.next : null,
    l2 ? l2.next : null,
    Math.floor(sum / 10)
  );
  
  return node;
}

递归的思路：每次处理一位，把进位传递给下一层递归。

边界情况 ​

  • 长度不同：[1], [9,9] → [0,0,1]，短链表用 0 补
  • 最高位进位：[5], [5] → [0,1]，carry 条件很关键
  • 全是 9：[9,9], [1] → [0,0,1]，连续进位
  • 0 + 0：[0], [0] → [0]，正常处理

常见错误 ​

错误1：忘记最高位进位

javascript
// ❌ 循环条件漏了 carry
while (l1 !== null || l2 !== null) { ... }
// 输入 [5], [5] 会输出 [0] 而不是 [0,1]

错误2：指针移动不安全

javascript
// ❌ 可能空指针异常
l1 = l1.next;
l2 = l2.next;

// ✅ 先检查
if (l1) l1 = l1.next;
if (l2) l2 = l2.next;

错误3：进位计算用错方法

javascript
// ❌ 取整方式错误
carry = sum / 10;  // 会得到小数 0.7

// ✅ 向下取整
carry = Math.floor(sum / 10);

技巧总结 ​

这道题的核心技巧：

  • 逆序存储的优势：个位在前，符合加法顺序
  • 哨兵节点：简化链表构建
  • 三条件循环：l1、l2、carry 缺一不可
  • 空值处理：用 0 代替已遍历完的链表

这道题是链表和数学结合的经典例题。理解了这个模式，你可以轻松处理类似的"字符串相加"、"大数乘法"等问题。

拓展思考 ​

  • LeetCode 445：两数相加 II（正序存储，需要先反转或用栈）
  • LeetCode 415：字符串相加（同样的逐位相加思路）
  • 如果要实现大数乘法呢？思路会有什么变化？

关联题目 ​

  • LeetCode 66：加一
  • LeetCode 67：二进制求和
  • LeetCode 369：给单链表加一

在 GitHub 上编辑此页