快慢指针与多指针——玩转链表复杂操作|算法篇

# 快慢指针与多指针

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 是未处理后缀的头。若说不出这句话，代码里的三四个指针很容易错位。

面试官追问

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

参考回答

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

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

参考回答

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

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

参考回答

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

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

参考回答

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

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

参考回答

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

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

参考回答

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

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

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

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

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

30 秒速记

dummy 让删除头结点也拥有前驱；fast 与 slow 都从 dummy 开始
fast 先走 n 步，再让两者同速前进；不变量是 fast 始终领先 slow n 个结点
当 fast 到最后一个结点时，slow 正好位于倒数第 n 个结点的前驱，执行 slow.next = slow.next.next
一趟扫描时间 O(L)、额外空间 O(1)；两趟“先数长度再定位”也为 O(L)，区别是遍历次数和流式能力
生产函数要处理 n 非正、n 大于长度、空链和成环输入，不能只依赖题目“n 有效”

我会让 fast 和 slow 都从 dummy 出发，先让 fast 走 n 步，再同步移动，最后删除 slow.next。 因为两者始终相差 n 个结点，所以 fast 到达链尾时，slow 正好停在待删结点的前驱。dummy 能统一处理删除头结点的情况，整套操作时间是 O(L)、额外空间是 O(1)。公共函数还要明确处理空链、非法 n、n 超过长度以及成环输入。

function removeNthFromEnd(head, n) {
  if (!Number.isInteger(n) || n <= 0) throw new RangeError('n must be positive')
  const dummy = { next: head }
  let fast = dummy
  let slow = dummy
  for (let step = 0; step < n; step += 1) {
    fast = fast.next
    if (fast === null) throw new RangeError('n exceeds list length')
  }
  while (fast.next !== null) {
    fast = fast.next
    slow = slow.next
  }
  slow.next = slow.next.next
  return dummy.next
}

@前端进阶之旅: 代码已经复制到剪贴板

使用 dummy 后，长度为 L 且 n=L 时，fast 走到原链尾，slow 仍停在 dummy，恰好删除原 head。题库通常保证 n 有效；公共函数必须明确非法输入是抛错、返回原链还是结构化失败。

真题描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个结点后，链表变为 1->2->3->5.

说明：给定的 n 保证是有效的。

思路分析

小贴士：dummy 结点的使用

上一节我给大家介绍了 dummy 结点：它可以帮我们处理掉头结点为空的边界问题，帮助我们简化解题过程。因此涉及链表操作、尤其是涉及结点删除的题目（对前驱结点的存在性要求比较高），我都建议大家写代码的时候直接把 dummy 给用起来，建立好的编程习惯：

const dummy = new ListNode()
// 这里的 head 是链表原有的第一个结点
dummy.next = head

@前端进阶之旅: 代码已经复制到剪贴板

“倒数”变“正数”

链表的删除我们上节已经讲过，相信都难不倒大家。这道题的难点实际在于这个“倒数第 N 个”如何定位。

考虑到咱们的遍历不可能从后往前走，因此这个“倒数第 N 个” 咱们完全可以转换为“正数第 len - n + 1"个。这里这个 len 代表链表的总长度，比如说咱们链表长为 7，那么倒数第 1 个就是正数第 7 个。按照这个思路往下分析，如果走直接遍历这条路，那么这个 len 就非常关键了。

我们可以直接遍历两趟：第一趟，设置一个变量 count = 0，每遍历到一个不为空的结点，count 就加 1，一直遍历到链表结束为止，得出链表的总长度 len；根据这个总长度，咱们就可以算出倒数第 n 个到底是正数第几个了（M = len - n + 1），那么我们遍历到第 M - 1（也就是 len - n）个结点的时候就可以停下来，执行删除操作（想一想，为什么是第 M-1 个，而不是第 M 个？如果你认真读了我们前面的章节，心中一定会有一个清晰的答案^_^）

不过这种超过一次的遍历必然需要引起我们的注意，我们应该主动去思考，“如果一次遍历来解决这个问题，我可以怎么做？”，这时候，就要请双指针法来帮忙了。

快慢指针登场

按照我们已经预告过的思路，首先两个指针 slow 和 fast，全部指向链表的起始位——dummy 结点：

快指针先出发！闷头走上 n 步，在第 n 个结点处打住，这里 n=2：

然后，快慢指针一起前进，当快指针前进到最后一个结点处时，两个指针再一起停下来：

此时，慢指针所指的位置，就是倒数第 n 个结点的前一个结点：

我们基于这个结点来做删除，可以说是手到擒来：

到这里，我们总结一下：

链表删除问题中，若走两次遍历，我们做了两件事：

求长度
做减法，找定位。

若用快慢指针，我们其实是把做减法和找定位这个过程给融合了。通过快指针先行一步、接着快慢指针一起前进这个操作，巧妙地把两个指针之间的差值保持在了“n”上（用空间换时间，本质上其实就是对关键信息进行提前记忆，这里咱们相当于用两个指针对差值实现了记忆），这样当快指针走到链表末尾（第 len 个）时，慢指针刚好就在 len - n 这个地方稳稳落地。

编码实现

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
const removeNthFromEnd = function(head, n) {
    // 初始化 dummy 结点
    const dummy = new ListNode()
    // dummy指向头结点
    dummy.next = head
    // 初始化快慢指针，均指向dummy
    let fast = dummy
    let slow = dummy

    // 快指针闷头走 n 步
    while(n!==0){
        fast = fast.next
        n--
    }
    
    // 快慢指针一起走
    while(fast.next){
        fast = fast.next
        slow = slow.next
    }
    
    // 慢指针删除自己的后继结点
    slow.next = slow.next.next
    // 返回头结点
    return dummy.next
};

@前端进阶之旅: 代码已经复制到剪贴板