链表

链表双指针

一个共同的思路：让两个指针拉开距离

链表不能随机访问，所以「倒数第 k 个」「中间那个」这类位置没法直接算。 双指针的办法是：让两个指针以某种固定关系一起走，等其中一个到头时， 另一个恰好停在你要的位置。

关系有两种：

  • 差 k 步（同速）→ 找倒数第 k 个
  • 速度差一倍（快的每次两步）→ 找中点、判环

找倒数第 k 个：先让快指针走 k 步

function findFromEnd(head, k) {
  let fast = head;
  for (let i = 0; i < k; i++) {
    if (fast === null) return null;   // 链表比 k 还短
    fast = fast.next;
  }

  let slow = head;
  while (fast !== null) {             // 两个同速走，差距保持 k
    fast = fast.next;
    slow = slow.next;
  }
  return slow;
}

⭐ 配上 dummy 就能一趟删除倒数第 k 个节点 —— 因为要删除就得拿到它的前驱， 而从 dummy 出发走同样的步数，slow 恰好停在前驱上：

function removeNthFromEnd(head, n) {
  const dummy = { val: 0, next: head };
  let fast = dummy, slow = dummy;
  for (let i = 0; i <= n; i++) fast = fast.next;   // 注意是 <=
  while (fast !== null) { fast = fast.next; slow = slow.next; }
  slow.next = slow.next.next;
  return dummy.next;
}

🚨 i <= n 而不是 i < n。多走那一步，slow 才会停在待删节点的前一个。

写成 i < n 会有两种完全不同的症状，取决于删的是不是最后一个：

[1,2,3,4,5] 删倒数第 2
  i <= n → [1,2,3,5]   ✅ 删掉了 4
  i <  n → [1,2,3,4]   ❌ 删掉了 5，往后错了一位

[1,2,3] 删倒数第 1
  i <= n → [1,2]
  i <  n → 💥 TypeError: Cannot read properties of null

⚠️ 一个安静地删错节点，一个直接崩 —— 而崩的那个反倒是好事， 至少你知道出问题了。真正危险的是第一种：链表长度对、只是内容错了一位， 不逐个比对根本看不出来。

3000 组随机（长度 1~10、n 随机取）看两种症状各占多少：

安静地删错一位   2129 组 = 71.0%
直接崩           871 组 = 29.0%
碰巧和正确答案一样     0 组

🚨 七成是安静地错，而且没有一组碰巧蒙对 —— 也就是说这个 bug 每次都在生效， 只是七成的时候不吭声。 ⭐ 那 29% 的崩溃全部来自「删的正好是倒数第 1 个」：那时 slow 停在最后一个节点上， slow.next.next 就是对 null 取属性。

找中点：fast 走两步

function middleNode(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

🚨 循环条件必须同时判 fast 和 fast.next，而且顺序不能反。

⭐ 有意思的是，两种漏写的崩溃条件正好互补。把四种写法在长度 1~6 上各跑一遍：

长度            1     2     3     4     5     6
完整条件        ok    ok    ok    ok    ok    ok
只判 fast       💥    ok    💥    ok    💥    ok      ← 奇数崩
只判 fast.next  ok    💥    ok    💥    ok    💥      ← 偶数崩
顺序写反        ok    💥    ok    💥    ok    💥      ← 同上
  • 只判 fast（漏了 fast.next）：奇数长度时 fast 会落在最后一个节点上， fast.next.next 对 null 取属性 → 崩
  • 只判 fast.next（漏了 fast）：偶数长度时 fast 会变成 null， 下一轮判 fast.next → 崩
  • 顺序写反（fast.next !== null && fast !== null）：行为与上一条完全相同 —— fast.next 先求值，fast 那个判断永远来不及生效。短路求值救不了写反的顺序。

🚨 所以只测一种奇偶，必然漏掉其中一个错法。 [1,2,3] 能跑通「只判 fast.next」，[1,2,3,4] 能跑通「只判 fast」—— 两个都测才有意义。

⭐ 偶数长度时中点取左还是取右，由循环条件决定

这是这一节最实用的一条，而且很多人不知道它是可控的：

while (fast !== null && fast.next !== null)          // → 取右中点
while (fast.next !== null && fast.next.next !== null) // → 取左中点

[1,2,3,4] 上，前者返回 3，后者返回 2。

📌 什么时候需要左中点？要把链表从中间切成两半的时候 —— 归并排序链表、判断回文链表。你需要的是「前半段的最后一个节点」， 好在那里断开；拿到右中点就断不了，因为你没有它的前驱。

⚠️ 拿奇数长度的链表测试，两种写法返回的是同一个节点。 长度 1~20 逐个跑一遍：

奇数长度（10 个）   10/10 两种写法返回同一节点
偶数长度（10 个）    0/10 相同 —— 每一个都不同

⭐ 分得干干净净：只有偶数长度才看得见差别。 又一个「测试用例选错就发现不了」的地方 —— 而且这次连「碰巧」的余地都没有。

判环：快慢指针会相遇

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

有环的话，快指针每轮比慢指针多走一步，两者距离每轮缩小 1，最终必然相遇 —— 就像操场上跑得快的人一定会套圈跑得慢的人。没环的话，快指针先撞到 null。

⚠️ if (slow === fast) 必须放在两个指针都移动之后。 放在前面的话，初始时 slow === fast === head，第一轮就返回 true。

⭐ 找环起点：相遇后把一个指针放回头部

function detectCycle(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      // 相遇了。把 slow 放回头部，两个指针同速走
      slow = head;
      while (slow !== fast) { slow = slow.next; fast = fast.next; }
      return slow;                    // 再次相遇的地方就是环起点
    }
  }
  return null;
}

为什么成立，一行推导：设头到环起点是 a 步，环起点到相遇点是 b 步，环长 c。 相遇时慢指针走了 a + b，快指针走了它的两倍，且多绕了整数圈：

2(a + b) = a + b + k·c    →    a + b = k·c    →    a = k·c − b

k·c − b 正是「从相遇点继续走到环起点」的距离（绕 k 圈再退 b 步）。 所以从头走 a 步和从相遇点走 a 步，会同时到达环起点。

📌 不用记推导，记结论就行：相遇后把一个指针放回 head，同速走，再遇即起点。

实测把「链表长度 1~40 × 环起点取遍每个位置（含无环）」全跑一遍， 860 种组合全部正确。那条推导也抽样验过：n=12、环起点在 5 时 a=5, b=2, c=7，(a+b)/c = 1 恰好是整数 —— 与 a + b = k·c 一致。

两个链表的相交节点

题意：两条链表可能在某个节点之后合并成一条，找出那个交点。

function getIntersectionNode(a, b) {
  let p = a, q = b;
  while (p !== q) {
    p = p === null ? b : p.next;   // 走完 A 就接着走 B
    q = q === null ? a : q.next;   // 走完 B 就接着走 A
  }
  return p;                         // 相交则是交点，不相交则同时为 null
}

⭐ 原理：两个指针走的总长度都是 lenA + lenB，所以一定会在同一时刻到达终点。 如果有交点，它们会在交点相遇；没有交点，就同时变成 null 一起退出。

🚨 换句话说，这段代码不需要单独处理「不相交」的情况 —— 它自然收敛到 null。 实测「两条链长度各 0~6 × 共享段长 0/1/3」共 147 种组合，全部正确（含不相交）。

⚠️ 但如果把 p === null ? b : p.next 写成 p.next === null ? b : p.next， 不相交时两个指针会永远错开一位，变成死循环。 差别就在于「走到 null 这一步算不算一步」。

长 3 与长 4，不相交      正确版 → null      错法 → 💥 死循环
长 2 与长 3，共享 2 个    正确版 → 交点      错法 → 交点（照样对）

🚨 相交时那个错法给的答案是对的。 所以如果你的测试用例全都相交 （而「找交点」这道题的用例往往都相交），它一次都不会暴露 —— 一上线碰到不相交的输入就直接挂死。 ⭐ 判据：凡是「靠走到 null 来同步两个指针」的写法， 必须专门测一组不相交的输入。

👉 递归反转，为下一章铺路

到这里为止全是迭代。链表还有一件事天然适合递归 —— 反转：

function reverse(head) {
  if (head === null || head.next === null) return head;
  const newHead = reverse(head.next);   // 相信它：后面那段已经反转好了
  head.next.next = head;
  head.next = null;
  return newHead;
}

⭐ 这是全书第一次真正需要「相信递归定义」而不是在脑子里展开 —— 下一章 递归与二叉树从这里接着讲， 而二叉树是后面几乎所有算法的枢纽。

练习

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

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