快慢指针与多指针

⚡ 30 秒速记

• 链表不能按下标访问，就用几个指针的相对位置记状态
• 固定间距（先走 n 步再同速）→ 倒数第 n 个
• 速度差（一步对两步）→ 判环、找中点
• 同速多指针（prev / cur / next）→ 反转，维护「已处理 / 未处理」两段
• 移动前先判空：fast、fast.next 要看清楚访问几层；几个指针仍是 O(1) 空间

快慢指针和多指针说白了就是：链表没法随机访问，那就用几个指针之间的位置关系把需要的信息存下来。 删倒数第 n 个，存的是两个指针相隔 n 步；判环、找中点，用的是一个走一步一个走两步的速度差；反转链表，prev 指着已经反转好的那段，cur 指着还没处理的那段。写代码前我会先用一句话说清每个指针代表什么，说不出来，代码基本会错位。

链表无法按下标随机访问，指针的相对位置就是算法状态。写代码前应先说出不变量：例如删除倒数结点时 fast 与 slow 的间距始终为 n；反转时 prev 是已反转前缀的头，current 是未处理后缀的头。若说不出这句话，代码里的三四个指针很容易错位。

💬 面试官追问

• 删倒数第 n 个结点，候选人让 fast 每次走两步、slow 走一步，对吗？

  不对。这题靠的是固定间距：fast 先走 n 步，然后两个一起一步一步走。一步对两步是判环和找中点用的，套错了位置就算错。

• 三个指针算不算 O(1) 空间？要不要改递归减少变量？

  算。指针个数是固定的，不随链表长度变。递归反而每层一个栈帧，是 O(n)，长链还会爆栈。

• 快指针每次走两步，循环条件写 while (fast) 行吗？

  不行。fast 不为空但 fast.next 为空时，fast.next.next 就报错了。走两步要写 while (fast && fast.next)。

• 找中点，偶数长度时返回的是左中点还是右中点？

  看初始化。slow、fast 都从 head 出发、条件 fast && fast.next，偶数时停在右中点；想要左中点就改成 fast.next && fast.next.next。用之前得先约定好。

链表题目中，有一类会涉及到反复的遍历。涉及反复遍历的题目，题目本身虽然不会直接跟你说“你好，我是一道需要反复遍历的题目”，但只要你尝试用常规的思路分析它，你会发现它一定涉及反复遍历；同时，涉及反复遍历的题目，还有一个更明显的特征，就是它们往往会涉及相对复杂的链表操作，比如反转、指定位置的删除等等。

解决这类问题，我们用到的是双指针中的“快慢指针”。快慢指针指的是两个一前一后的指针，两个指针往同一个方向走，只是一个快一个慢。快慢指针严格来说只能有俩，不过实际做题中，可能会出现一前、一中、一后的三个指针，这种超过两个指针的解题方法也叫“多指针法”。

快慢指针+多指针，双管齐下，可以帮助我们解决链表中的大部分复杂操作问题。

快慢指针——删除链表的倒数第 N 个结点