0. 链表算法常用技巧

链表题的核心不是复杂语法，而是处理好指针关系。做题时重点关注三件事：

  • 当前节点是谁。
  • 下一个节点是否需要提前保存。
  • 修改 next 后，链表会不会断掉或成环。

虚拟头节点 dummy

当题目涉及删除、插入、合并、重新拼接链表时，经常使用虚拟头节点。

const dummy = new ListNode(0);
dummy.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;

常见题型：

  • 删除链表元素
  • 删除倒数第 N 个节点
  • 合并两个有序链表
  • 两两交换链表节点

保存 next

只要要修改当前节点的 next 指针，就要先思考是否需要保存后续链表。

const next = cur.next;
cur.next = prev;
prev = cur;
cur = next;

如果不提前保存 next，执行 cur.next = prev 后，原本的后半段链表可能就找不到了。

常见题型：

  • 反转链表
  • 反转链表 II
  • K 个一组反转链表
  • 两两交换链表节点

快慢指针

快慢指针常用来处理“位置关系”问题。

let slow = head;
let fast = head;

while (fast !== null && fast.next !== null) {
  slow = slow.next;
  fast = fast.next.next;
}

slow 每次走一步，fast 每次走两步。当 fast 到达链表尾部时，slow 通常在链表中间。

常见用途：

  • 找链表中点
  • 判断链表是否有环
  • 找环的入口
  • 排序链表中切分左右两段

注意：不同题目里 fast 的初始位置可能不同。

在排序链表中，经常写成：

let slow = head;
let fast = head.next;

这样可以让 slow 停在左半部分的尾节点，方便执行：

const rightHead = slow.next;
slow.next = null;

如果两个节点时 fast 从 head 开始，slow 可能停在最后一个节点，导致链表没有被真正拆开。

前后指针

前后指针通常让两个指针保持固定距离。

例如删除倒数第 N 个节点：

const dummy = new ListNode(0);
dummy.next = head;

let fast = dummy;
let slow = dummy;

for (let i = 0; i < n; i++) {
  fast = fast.next;
}

while (fast.next !== null) {
  fast = fast.next;
  slow = slow.next;
}

slow.next = slow.next.next;

return dummy.next;

核心是让 fast 先走 n 步，然后 fast 和 slow 一起走。当 fast 到尾部时，slow.next 就是要删除的节点。

常见题型：

  • 删除倒数第 N 个节点
  • 找链表倒数第 K 个节点
  • 判断链表是否相交

双指针消除长度差

两个链表长度不同时，可以通过“双指针换头”消除长度差。

let pA = headA;
let pB = headB;

while (pA !== pB) {
  pA = pA === null ? headB : pA.next;
  pB = pB === null ? headA : pB.next;
}

return pA;

如果两个链表相交，两个指针最终会在交点相遇；如果不相交，两个指针最终都会变成 null。

常见题型：

  • 相交链表

原地反转

反转链表的核心动作是：

cur.next = prev;

完整模板：

let prev = null;
let cur = head;

while (cur !== null) {
  const next = cur.next;
  cur.next = prev;
  prev = cur;
  cur = next;
}

return prev;

常见题型：

  • 反转链表
  • 反转链表 II
  • K 个一组反转链表

拆分链表

拆分链表时，关键是先保存下一段的头节点，再断开当前链表。

const nextHead = cur.next;
cur.next = null;

不能先断开再保存，否则后面的链表会丢失。

常见题型：

  • 排序链表
  • 分隔链表
  • K 个一组反转链表

合并链表

合并两个有序链表时，常用 dummy 和 cur。

const dummy = new ListNode(0);
let cur = dummy;

while (list1 !== null && list2 !== null) {
  if (list1.val <= list2.val) {
    cur.next = list1;
    list1 = list1.next;
  } else {
    cur.next = list2;
    list2 = list2.next;
  }

  cur = cur.next;
}

cur.next = list1 === null ? list2 : list1;

return dummy.next;

常见题型：

  • 合并两个有序链表
  • 合并 K 个升序链表
  • 排序链表

链表题检查清单

写完链表题后，可以按下面几项检查：

  • 是否需要 dummy 处理头节点变化。
  • 修改 next 前，是否需要先保存后续节点。
  • 循环条件是看 cur，还是看 cur.next。
  • 返回的是 head、dummy.next，还是反转后的 prev。
  • 链表是否被正确断开，避免递归无法缩小规模。
  • 是否可能出现空指针访问，例如 fast.next.next 前没有判断 fast.next。

常见模板选择

场景常用技巧
删除节点dummy + cur.next
反转链表prev + cur + next
找中点快慢指针
判断有环快慢指针
找倒数第 N 个前后指针
合并有序链表dummy + 尾指针
排序链表快慢指针拆分 + 归并合并
相交链表双指针换头