快慢指针：核心思想与解题模板
快慢指针的本质是用两个指针的间距来记录位置信息，避免额外数组存储。
核心哲学
“与其存下来，不如走过去。”
当你需要找链表中某个特定位置的节点时，最直觉的做法是把所有节点存进数组，按下标取。但这要 O(n) 空间。
快慢指针的思路是：让一个指针先走几步，另一个指针后走，两个指针的间距就是你需要的偏移量。 当先走的指针到达末尾时，后走的指针恰好停在你想要的位置。
四种常见模式
模式一：找倒数第 k 个节点
fast 先走 k 步，然后 fast 和 slow 一起走，fast 到 null 时 slow 就是倒数第 k 个。
初始： [1] [2] [3] [4] [5] → null
↑ slow
↑ fast（先走了 k=2 步）
结束： [1] [2] [3] [4] [5] → null
↑ slow ↑ fast
slow 在倒数第 k 个位置
如果要删除倒数第 k 个，fast 先走 k+1 步，这样 slow 停在被删节点的前一个（需要改 next 指针才能删除）。
为什么是 k+1 不是 k？
如果 fast 先走 k 步，fast 和 slow 一起走到 fast 为 null 时，slow 指向被删节点本身。但删除操作需要前一个节点的 next 指针，所以 fast 要多走一步，让 slow 停在被删节点的前一个。
经典题：10. One-Pass Removal of k-th Node from End
模式二：判断链表是否有环
fast 每次走两步，slow 每次走一步。如果有环，fast 一定会追上 slow（在环里转圈迟早相遇）。如果无环，fast 先到 null。
slow: 1 → 2 → 3 → 4 → 5 → 3（回到环入口）
fast: 1 → 3 → 5 → 3 → 5 → 3（追上 slow）
为什么 fast 一定能追上 slow？
假设环外长度 a，环长度 b。slow 进环时 fast 已经在环里了。fast 每步追近 slow 一格（fast 走 2 步，slow 走 1 步，相对速度 1），环长 b 步，最多 b 步内一定追上。
模式三：找链表中点
fast 每次走两步，slow 每次走一步。fast 到末尾时 slow 在中点。
slow: 1 → 2 → 3
fast: 1 → 3 → 5 → null
slow 停在中间节点
用于归并排序链表、判断回文链表。
细节：如果节点数是偶数，slow 停在前半段的最后一个节点（比如 5 个节点停在第 3 个，4 个节点停在第 2 个）。具体停在哪里取决于 fast 的终止条件（fast === null 还是 fast.next === null）。
模式四：找环的入口
先用模式二判断有环，相遇后让一个指针从 head 出发，另一个从相遇点出发，两个都每次走一步，再次相遇就是环入口。
数学证明：设环外长度 a，环入口到相遇点距离 b，相遇点到环入口距离 c。
- slow 走了 a + b 步
- fast 走了 a + b + n(b+c) 步（在环里转了 n 圈）
- fast 是 slow 的两倍：2(a+b) = a + b + n(b+c)
- 化简：a = (n-1)(b+c) + c
- 即：a = n圈 + c，所以从 head 走 a 步 = 从相遇点走 n 圈 + c 步，两者在环入口相遇
解题模板
function fastSlowPointer(head: ListNode): ListNode | null {
let fast = head
let slow = head
// fast 先走 k 步（模式一）
for (let i = 0; i < k; i++) {
if (!fast) return head // k 越界
fast = fast.next
}
// fast 和 slow 一起走
while (fast) {
fast = fast.next
slow = slow.next
}
// slow 现在在目标位置
return slow
}复杂度
- 时间：O(n)，一次遍历。
- 空间：O(1)，只用两个指针。
这是快慢指针最大的优势：不额外存节点，只用两个指针的间距来定位。 和用数组存节点的方法相比，空间从 O(n) 降到 O(1)。
总结
遇到需要找链表中特定位置的问题，先问自己：
- 我要找的位置是倒数第几个？→ fast 先走 k 步。
- 要删除还是只读取？删除 → fast 先走 k+1 步（slow 要停在前一个）。
- 能不用数组？能 → 快慢指针，空间 O(1)。
想清楚这三点，再动笔写代码。