快慢指针与多指针

⚡ 30 秒速记

• 快慢指针不是固定速度名词，而是用两个位置编码距离、阶段或环内相对运动
• 固定间距可定位倒数位置，速度差可检测环，同速多指针可维护待处理区间和已处理前缀
• 每个指针都要有一句语义，例如 fast 指向前方第 n 个位置、slow 指向目标前驱，不能只背变量名
• 移动前先检查可达性；链表边界常见 fast、fast.next 与 fast.next.next 三种条件，不能互换
• 多指针通常只用 O(1) 引用空间，但仍可能走 O(n) 时间；空间换时间并不是所有双指针题的准确描述

快慢指针和多指针的本质，是用几个指针的相对位置保存链表遍历过程中的状态。 因为链表不能按下标随机访问，写代码前要说清每个指针的不变量，例如删除倒数结点时，fast 与 slow 的间距始终为 n。遇到反转时，也可以让 prev 表示已反转前缀的头，current 表示尚未处理后缀的头，避免多个指针发生错位。移动前还要按实际访问层级检查 fast、fast.next 等边界；这类方法通常只占 O(1) 引用空间，但遍历时间仍可能是 O(n)。

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

💬 面试官追问

• 候选人在删除倒数第 n 个结点时固定让 fast 每轮走两步、slow 走一步；你会如何指出这不是通用的快慢指针规则？

  删除倒数结点需要的是 fast 与 slow 始终保持 n 个结点的间距，因此应先建立间距，再让两者同速前进。2:1 速度常服务于环检测，机械套用会破坏当前任务的不变量并删错位置。

• 一个链表编辑页面要原地删除倒数结点，代码评审时你会要求开发者在循环旁写清哪条不变量？

  应写清 fast 与 slow 的间距始终为 n，以及当 fast 到达链表末端时 slow 对应待删除位置的关系。代码中的初始化、提前移动和终止条件都要围绕这句话验证，否则头结点等边界容易错位。

• 需求从删除倒数结点改成原地反转链表，原来的双指针角色还能保持不变吗？

  不能只替换变量名，反转时需要维护“prev 是已反转前缀的头，current 是未处理后缀的头”这一状态。更新 current.next 前还要暂存后继结点，否则未处理部分会丢失；指针数量相近不代表不变量相同。

• 线上偶发链表断裂，日志显示执行过 current.next = prev；你会优先检查哪一个更新顺序？

  优先确认修改 current.next 之前是否先保存原后继结点，以及随后是否按保存值推进 current。如果先改指向再读取后继，未处理后缀会丢失；若 prev 更新过早，也可能形成错误自环或跳过结点。

• 评审者认为使用三个指针就不再是 O(1) 空间，要求改成递归以“减少变量”；你会怎样裁决？

  固定数量的指针引用不会随链表长度增长，辅助空间仍是 O(1)，无需为了少一个局部变量改成递归。递归调用栈通常会随结点数增长，还引入深度风险；复杂度应看存储规模，而不是变量表面数量。

• 候选人同时做环检测、删除倒数结点和链表反转，你会要求他用什么共同视角串联三段代码？

  共同视角是把指针的相对位置和所指区间视为算法状态，并在每次移动后维持明确不变量。环检测关注速度关系，删除关注固定间距，反转关注已处理与未处理边界；三者共享方法，但不能共享同一移动规则。