链表两数相加

更新: 7/5/2026 字数: 0 字 时长: 0 分钟

题目描述

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

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

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807，逆序存储即 7 → 0 → 8

为什么是逆序？因为逆序存储时，链表头恰好是个位。做竖式加法时我们本来就是从个位（最低位）开始逐位相加、逐位进位，逆序存储让我们可以顺着链表方向一次遍历完成，无需反转。

思路拆解

暴力解法：先还原数字，再相加

最直觉的想法：把两个链表分别还原成整数，相加后再拆成链表。

点击展开暴力解法（不推荐）

// 把链表还原成数字 → 相加 → 再拆回链表
function addTwoNumbers(l1, l2) {
  const toNumber = (node) => {
    let num = 0n, base = 1n; // 用 BigInt 避免溢出
    while (node) {
      num += BigInt(node.val) * base;
      base *= 10n;
      node = node.next;
    }
    return num;
  };

  let sum = toNumber(l1) + toNumber(l2);
  const dummy = new ListNode(0);
  let cur = dummy;
  if (sum === 0n) return new ListNode(0);
  while (sum > 0n) {
    cur.next = new ListNode(Number(sum % 10n));
    cur = cur.next;
    sum /= 10n;
  }
  return dummy.next;
}

为什么暴力解法不好？

链表长度可能达到几百上千位，远超 Number 甚至 Number.MAX_SAFE_INTEGER 的表示范围。即便用 BigInt 能保证正确性，也做了两趟无谓的"数字↔链表"转换，浪费时间和空间。本质上我们并不需要完整的数字，只需要逐位的结果。

最优解法：模拟竖式加法（一次遍历）

回到小学的竖式加法——我们从个位开始，每一位做 a + b + 进位，写下"个位数"，把"十位"作为进位带到下一位。

由于链表本就是逆序（头是个位），我们只需同步遍历两条链表，逐位相加即可：

核心思路

维护一个进位变量 carry。每一步取两条链表当前节点的值（走到尽头则记为 0），计算：

把"当前位"作为新节点接到结果链表尾部，进位带入下一轮。循环条件是 l1 或 l2 还没走完，或 carry 不为 0 —— 最后一个条件保证 [9]+[1]=[0,1] 这种进位溢出能被正确处理。

哑节点（dummy node）技巧

构造结果链表时，"第一个节点"是个特殊情况：它还不存在，head 是 null。为避免为"头节点是否为空"单独写分支，我们创建一个哑节点 dummy，让 cur 从它出发不断往后接，最终返回 dummy.next 即真正的头。这是链表题里最常用的简化技巧。

交互式动画演示

下面用样例 l1 = [2,4,3]、l2 = [5,6,4] 演示最优解法的完整过程。点击 下一步 逐步观察指针移动、carry 变化与结果链表的构建：

步骤 1 / 5

l1 (342)

2

→

4

→

3

→

null

+

进位 carry = 0

l2 (465)

5

→

6

→

4

→

null

结果

D

→（空）

初始化：进位 carry = 0，结果链表为空（哑节点在最前）。点击「下一步」开始逐位相加。

完整代码（JavaScript）

高亮行为算法核心：第 8 行取值兜底，第 10-12 行计算当前位与进位。

/**
 * 链表节点定义
 * function ListNode(val, next) {
 *   this.val = (val === undefined ? 0 : val);
 *   this.next = (next === undefined ? null : next);
 * }
 */

/**
 * @param {ListNode} l1  逆序存储的加数一
 * @param {ListNode} l2  逆序存储的加数二
 * @return {ListNode}    逆序存储的和
 */
function addTwoNumbers(l1, l2) {
  const dummy = new ListNode(0); // 哑节点，简化头节点处理
  let cur = dummy;               // 结果链表的构建游标
  let carry = 0;                 // 进位

  while (l1 || l2 || carry) {
    // 走到尽头的链表按 0 处理，保证不等长时也能相加
    const a = l1 ? l1.val : 0;
    const b = l2 ? l2.val : 0;

    const sum = a + b + carry;   // 当前位总和
    carry = Math.floor(sum / 10); // 计算新进位（0 或 1）
    cur.next = new ListNode(sum % 10); // 写下当前位

    cur = cur.next;              // 结果游标后移
    if (l1) l1 = l1.next;        // 各自后移（若还没走完）
    if (l2) l2 = l2.next;
  }

  return dummy.next; // 跳过哑节点，返回真正的头
}

复杂度分析

设两条链表长度分别为 、。

指标	复杂度	说明
时间复杂度		两条链表各遍历一次，循环次数取决于较长者（进位溢出至多多一次）
空间复杂度		除返回的结果链表外，仅用常数个变量。若把返回链表计入，则为

边界与易错点

常见踩坑

1. 循环条件漏掉 carry：写成 while (l1 || l2) 会导致 [9] + [1] 少一位，结果错误（应为 [0,1]）。最后的进位必须单独成一个节点。
2. 两链表不等长：短链表走完后应按 0 继续参与运算，不能直接停。代码中的 l1 ? l1.val : 0 就是为此兜底。
3. 忘记移动结果游标 cur：新建节点后必须 cur = cur.next，否则所有节点都挂在同一位置。
4. 不用哑节点导致的空指针判断：头节点为空时的特判很容易出错，哑节点能彻底规避。
5. 误以为可以直接转整数：链表可能极长，Number 会溢出丢精度；即便本题样例小，也应养成模拟竖式的习惯。

一句话总结

逆序存储 + 竖式模拟 + 哑节点 + 循环带 carry —— 四个关键词拿下这道链表经典题。