链表

链表的原理与基本操作

它和数组的差别只有一条

数组的元素在内存里连着，链表的不连。

别的差别全是这一条推出来的：

数组 链表
按下标访问 O(1)（地址能算出来） O(n)（只能从头走）
已知位置后增删 O(n)（后面全要挪） O(1)（改两个指针）
内存 连续一整块 零散，每个节点多存一个指针

🚨 「链表增删是 O(1)」这句话默认你已经站在那个位置上了。 题目要是给「删除第 k 个节点」，你还得先花 O(n) 走过去 —— 总成本仍是 O(n)。 链表真正快的是「我手里有这个节点的引用，把它摘掉」。

这个差距实测有多大

在中间位置删 1000 次（链表已持有该位置的引用，数组用 splice）：

n 摘 1000 个节点 splice 1000 次 建链一次
10,000 0.012 ms 0.4 ms 0.1 ms
100,000 0.010 ms 6.6 ms 0.6 ms
1,000,000 0.011 ms 67.1 ms 28.1 ms

⭐ 摘节点那一列完全不随 n 变化（0.010~0.012 ms），splice 那列线性增长 —— 教科书的结论在这里成立得很干净，n=100 万时差 6000 倍。

⚠️ 但看最后一列：光把这条链建出来就要 28.1 ms，够 splice 跑 400 多次。 所以真实判据不是「谁的单次操作快」，而是**「你本来就持有链表吗」**：

  • 数据已经是链表（题目给的、LRU 里挂着的）→ 摘节点白赚
  • 数据是数组，为了删得快特意转成链表 → 转换成本远超省下的

📌 面试问「数组和链表怎么选」，答这一条就够： 随机访问多用数组；已经持有位置引用、且频繁增删用链表。

三种形态

// 单链表：只能往后走
const node  = { val: 1, next: null };

// 双链表：能往回走，代价是每个节点多一个指针
const dnode = { val: 1, prev: null, next: null };

// 循环链表：尾节点的 next 指回头节点

⭐ 面试题里绝大多数是单链表。双链表主要出现在设计题里 —— LRU 缓存要做到 O(1) 删除任意节点，就必须能从这个节点找到它的前驱。

⭐ 虚拟头结点：链表题里最划算的技巧

链表最烦人的地方是头节点没有前驱，于是「删掉头节点」永远要单独写一个分支。

dummy 就是在真头节点前面挂一个假节点，让每个真实节点都有前驱：

function removeElements(head, val) {
  const dummy = { val: 0, next: head };   // ← 假头
  let cur = dummy;

  while (cur.next !== null) {
    if (cur.next.val === val) cur.next = cur.next.next;
    else cur = cur.next;
  }

  return dummy.next;                       // ← 真头可能已经变了
}

对照不用 dummy 的写法：

function removeElementsNoDummy(head, val) {
  // 先单独处理开头连续的目标值
  while (head !== null && head.val === val) head = head.next;
  if (head === null) return null;

  let cur = head;
  while (cur.next !== null) {
    if (cur.next.val === val) cur.next = cur.next.next;
    else cur = cur.next;
  }
  return head;
}

多出来的三行全是边界处理，而且每一行都是错误高发点。两种错法都实测过：

① 第一行写成 if 而不是 while
   [6,6,1,2] 删 6  →  dummy 版得 [1,2]，if 版得 [6,1,2]
                       ↑ 开头连续两个 6 只删掉一个

② 漏掉 head === null 那行
   [7,7,7] 删 7   →  TypeError: Cannot read properties of null (reading 'next')
                       ↑ 整条链都被删空，cur 是 null 还去读 cur.next

⭐ 注意这两个 bug 的触发条件都很窄：一个要「开头连续出现两次」， 一个要「整条链全是目标值」。随手造几个用例基本碰不到， 而 dummy 版根本不存在这两个分支，也就无从写错。

⭐ 判据：只要头节点有可能被删掉或换掉，就上 dummy。 删除、合并、插入、分割链表 —— 一律先写 const dummy = { next: head }。

⚠️ 最后要 return dummy.next 而不是 return head。 head 那个变量在过程中可能已经被摘掉了，返回它会丢掉整条链的开头。

反转链表：迭代

function reverseList(head) {
  let prev = null;
  let cur = head;

  while (cur !== null) {
    const next = cur.next;   // 🚨 必须先存下来
    cur.next = prev;         // 掉头
    prev = cur;              // 两个指针一起前进
    cur = next;
  }

  return prev;               // cur 走到 null 时，prev 就是新的头
}

🚨 const next = cur.next 不能省，也不能挪到 cur.next = prev 后面。 那一行一执行，原来的后继就永久丢失 —— 没有任何办法找回来， 链表从这里断成两截。

⚠️ 症状很有迷惑性：返回的链表只剩一个节点。看起来像循环没跑起来， 实际是第一轮就把路砍断了。实测把那行挪到 cur.next = prev 后面：

正确版反转 6 个节点   [5,4,3,2,1,0]
挪到掉头之后          [0]            ← 只剩原来的头
长度 2 / 3 / 10 / 100 的链   结果全是「只剩 1 个」

⭐ 为什么恒为 1：掉头后 cur.next 已经等于 prev，所以 next 拿到的是 刚处理完的那个节点；cur = next 让它在原地打转一步就退出。 第一轮结束时 prev 是原 head、而它的 next 已被置 null。

📌 返回 prev 不是 cur。循环结束时 cur === null，prev 停在最后一个节点上， 那正是反转后的新头。

反转链表：递归

同一件事的递归写法。每一步的推导见 怎么理解递归：

function reverseList(head) {
  if (head === null || head.next === null) return head;
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

⚠️ 递归版更短，但空间是 O(n)（调用栈），迭代版是 O(1)。 「占栈」不是理论问题 —— 二分探测实测（Node v22.22.3）：

递归版能处理的最大长度    7800 ~ 13700 个节点，再多就 RangeError
迭代版处理 200 万个节点    正常

⚠️ 那个区间不是测不准，是这个上限本来就会变：同一进程里首次探测得到 8592，第二次起稳定在 13737（差 1.60 倍）—— 冷启动时函数跑在解释器里、栈帧大， 被 JIT 优化后帧变小，同样的栈就能装更多层。 📌 详细的探测数据和尾递归优化那个陷阱在 怎么理解递归里。

🚨 按下限 7800 估：力扣链表题的数据规模到 5×10⁴， 也就是说递归版在部分题目上会直接栈溢出。

⭐ 面试写迭代版更稳，顺口补一句「递归版更短但占栈，长链会溢出」是加分。

合并两个有序链表

dummy 的又一个标准用法：

function mergeTwoLists(l1, l2) {
  const dummy = { val: 0, next: null };
  let tail = dummy;

  while (l1 !== null && l2 !== null) {
    if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
    else                  { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }

  // ⭐ 剩下的那条直接接上，不用逐个搬
  tail.next = l1 !== null ? l1 : l2;

  return dummy.next;
}

⭐ 最后那一行是链表独有的便宜：数组归并时剩余部分要逐个拷贝， 链表只要接一个指针。

📌 l1.val <= l2.val 里的等号决定稳定性，与 归并排序那条同理 —— 排数字看不出来，排对象才暴露。实测两条链 A = [{1,"A1"},{3,"A3"}]、B = [{1,"B1"},{3,"B3"}]：

用 <=    [A1, B1, A3, B3]     相等时取 l1，A 在前 = 稳定
用 <     [B1, A1, B3, A3]     相等时取 l2，两组的相对顺序被换了
换成纯数字 [1,3] 与 [1,3]      两种写法都得 [1,1,3,3] —— 完全看不出区别

⚠️ 最后一行才是重点：用数字测稳定性，等于没测。 要暴露它，被排序的元素必须携带「值以外的身份」。

下一步

两个指针在链表上一起跑，能做的事出奇地多 —— 链表双指针， 递归思维也由那一节引出。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。