链表中双指针

链表中双指针有哪几种配合方式？

模式	移动规则	典型用途
起点不一致	fast 先走 n 步, 之后同步走	倒数第 k 个结点
步长不一致	slow 走 1 步, fast 走 2 步	中点、判环、找入口
分离双指针	两个指针各指一条链表, 条件推进	合并、相交、长度对齐

• 共同前提: 只有单向 next, 因此只能"用距离换位置";

如何用起点不一致的快慢指针找倒数第 k 个结点？

• 思路: fast 先走 k 步, 之后 slow、fast 同步走, 直到 fast 触底;
• 位置关系: 两者间距恒为 k, fast 到底时 slow 正好指向倒数第 k 个;
• 哨兵: 删除类题目把哨兵算作第 0 个结点, 可自然覆盖"删第一个";
• 时间 $O(n)$, 空间 $O(1)$;

// 倒数第 k 个结点 (LCR 140)
const trainingPlan = (head, cnt) => {
  const dummy = new ListNode(-1, head);
  let slow = dummy;
  let fast = dummy;
  while (cnt !== 0) {
    fast = fast.next;
    cnt--;
  }
  while (fast) {
    slow = slow.next;
    fast = fast.next;
  }
  return slow;
};

// 删除倒数第 n 个结点 (19)
const removeNthFromEnd = (head, n) => {
  const dummy = new ListNode(-1, head);
  let left = dummy;
  let right = dummy;
  while (n !== 0) {
    right = right.next;
    n--;
  }
  while (right.next) {
    left = left.next;
    right = right.next;
  }
  left.next = left.next.next;
  return dummy.next;
};

如何用步长不一致的快慢指针找中点？

• 规则: slow 每次 1 步, fast 每次 2 步, fast 到底时 slow 落在中点;
• 偶数长度: 循环条件写成 fast && fast.next 时返回偏右的中点;
• 用途: 归并排序断开两半, 见 链表排序;

const middleNode = (head) => {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
};

分离双指针怎样对齐两条链表？

• 用途: 两条链表需要"同一相对位置"同时推进时, 先消掉长度差;
• 做法: 分别求长度 → 长链先走差值步 → 同步推进;
• 应用: 两个链表的遍历 中的相交链表;