讲解

链表用指针把分散的节点串成链：每个节点存一个值和一个 next 指针。与数组相反，它的性格是：随机访问 O(n)（只能从头走），但在已知位置插入删除是 O(1)（改两根指针即可）。头插、尾删、中间拼接都不需要搬动数据——这是它在某些场景（如 LRU 的顺序链表、操作系统内核）不可替代的原因。

链表题目的技巧高度套路化，掌握四招就够走天下。虚拟头节点（dummy）：在头节点前加一个假节点，让「删除头节点」和「删除中间节点」用同一套代码，免去特判；函数最后返回 dummy.next。双指针：快慢指针找中点（快两步慢一步，快走完慢在中点）、判环（有环则快慢必相遇）、找倒数第 k 个（快先走 k 步）。指针操作顺序：反转链表的关键是「先用临时变量存 next，再改指针，最后双针前移」，顺序错一步链就断了。递归视角：链表天然是递归结构（一个节点 + 一条更短的链表），反转、合并都能写出优雅的递归版，但要警惕深度。

判环的证明值得想一遍：快指针每次比慢指针多走一步，若有环，快指针进入环后相当于在追慢指针，距离每轮缩小 1，必然相遇；若无环，快指针先到达 null。这个「相对速度」的论证方式在面试中经常被要求口述。

示例

先给两个贯穿本章的工具函数（数组与链表互转，方便写断言），然后三个经典操作：反转链表、快慢指针判环、合并两个有序链表：

import assert from 'node:assert/strict';

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function fromArray(arr) {
  const dummy = new ListNode(0);
  let tail = dummy;
  for (const v of arr) {
    tail.next = new ListNode(v);
    tail = tail.next;
  }
  return dummy.next;
}

function toArray(head) {
  const out = [];
  while (head !== null) {
    out.push(head.val);
    head = head.next;
  }
  return out;
}

// 迭代反转：存 next、掉头、双针前移
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;
}

// 快慢指针判环：有环则相遇
function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

// 虚拟头节点合并两条有序链表
function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  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;
}

assert.deepStrictEqual(toArray(reverseList(fromArray([1, 2, 3, 4, 5]))), [5, 4, 3, 2, 1]);
assert.strictEqual(hasCycle(fromArray([1, 2, 3])), false);

// 手工造一个环：尾节点指回第二个节点
const cyc = fromArray([1, 2, 3, 4]);
let tail = cyc;
while (tail.next !== null) tail = tail.next;
tail.next = cyc.next;
assert.strictEqual(hasCycle(cyc), true);

assert.deepStrictEqual(toArray(mergeTwoLists(fromArray([1, 2, 4]), fromArray([1, 3, 4]))), [1, 1, 2, 3, 4, 4]);

console.log('链表示例全部通过');

对照 mergeTwoLists 体会虚拟头节点的价值：如果没有 dummy，「第一个节点选谁」就要单独分支处理；有了 dummy，所有节点的接入逻辑完全统一。

常见坑

  • 改指针前没存 next：cur.next = prev 之后 cur.next 就丢了，必须用临时变量先存——反转链表最高频错误。
  • 快指针越界：fast.next.next 之前必须确认 fast 和 fast.next 都不为 null，顺序也不能反。
  • 环形链表遍历死循环：toArray 这类遍历在有环时永不停止，调试判环代码时别把环链丢进遍历函数。
  • 忘记接剩余部分：合并两条链表循环结束后必有一条非空，tail.next 要接上它，漏了就丢数据。
  • 空链表特判遗漏：所有链表函数先想 head === null 的行为是否正确——好消息是上面这些写法天然兼容空链表。

小结

链表插入删除 O(1)、随机访问 O(n)；四招：虚拟头节点统一逻辑、快慢指针找中点判环、反转时先存 next、递归视角辅助理解。下一章看「后进先出」的结构：栈与单调栈。