# 快慢指针与多指针
30 秒速记
- 链表不能按下标访问，就用几个指针的相对位置记状态
- 固定间距（先走
n步再同速）→ 倒数第n个 - 速度差（一步对两步）→ 判环、找中点
- 同速多指针（
prev/cur/next）→ 反转，维护「已处理 / 未处理」两段 - 移动前先判空：
fast、fast.next要看清楚访问几层；几个指针仍是O(1)空间
快慢指针和多指针说白了就是：链表没法随机访问，那就用几个指针之间的位置关系把需要的信息存下来。 删倒数第 n 个，存的是两个指针相隔 n 步；判环、找中点，用的是一个走一步一个走两步的速度差；反转链表，prev 指着已经反转好的那段，cur 指着还没处理的那段。写代码前我会先用一句话说清每个指针代表什么，说不出来，代码基本会错位。
链表无法按下标随机访问，指针的相对位置就是算法状态。写代码前应先说出不变量：例如删除倒数结点时 fast 与 slow 的间距始终为 n；反转时 prev 是已反转前缀的头，current 是未处理后缀的头。若说不出这句话，代码里的三四个指针很容易错位。
面试官追问
追问 1删倒数第 n 个结点，候选人让 fast 每次走两步、slow 走一步，对吗？
不对。这题靠的是固定间距：fast 先走 n 步，然后两个一起一步一步走。一步对两步是判环和找中点用的，套错了位置就算错。
追问 2三个指针算不算 O(1) 空间？要不要改递归减少变量？
算。指针个数是固定的，不随链表长度变。递归反而每层一个栈帧，是 O(n)，长链还会爆栈。
追问 3快指针每次走两步，循环条件写 while (fast) 行吗？
不行。fast 不为空但 fast.next 为空时，fast.next.next 就报错了。走两步要写 while (fast && fast.next)。
追问 4找中点，偶数长度时返回的是左中点还是右中点？
看初始化。slow、fast 都从 head 出发、条件 fast && fast.next，偶数时停在右中点；想要左中点就改成 fast.next && fast.next.next。用之前得先约定好。
链表题目中，有一类会涉及到反复的遍历。涉及反复遍历的题目，题目本身虽然不会直接跟你说“你好，我是一道需要反复遍历的题目”，但只要你尝试用常规的思路分析它，你会发现它一定涉及反复遍历；同时，涉及反复遍历的题目，还有一个更明显的特征，就是它们往往会涉及相对复杂的链表操作，比如反转、指定位置的删除等等。
解决这类问题，我们用到的是双指针中的“快慢指针”。快慢指针指的是两个一前一后的指针，两个指针往同一个方向走，只是一个快一个慢。快慢指针严格来说只能有俩，不过实际做题中，可能会出现一前、一中、一后的三个指针，这种超过两个指针的解题方法也叫“多指针法”。
快慢指针+多指针，双管齐下，可以帮助我们解决链表中的大部分复杂操作问题。
# 快慢指针——删除链表的倒数第 N 个结点
30 秒速记
- 倒数第
n个 = 让fast先走n步，然后和slow同速走 fast到最后一个结点时，slow正好在待删结点的前驱- 两个指针都从
dummy出发，删头结点不用特判 - 循环条件是
fast.next !== null，起点、先走步数、终止条件三者绑定，改一个就错 - 两趟法（先数长度）也是
O(L)，快慢指针只是少遍历一趟
让 fast 先走 n 步，然后 fast 和 slow 一起走，fast 到链尾时，slow 刚好停在要删的那个结点前面。 原理就是两个指针一直隔着 n 步，等于把「倒数第 n 个」翻译成了「离末尾 n 步」。两个指针都从 dummy 出发，这样要删的是头结点时，slow 停在 dummy 上，slow.next = slow.next.next 照样成立。时间 O(L)、空间 O(1)。
// 1->2->3->4->5, n = 2
removeNthFromEnd(head, 2) // 1->2->3->5
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
};
面试官追问
