# 快慢指针与多指针
链表题目中，有一类会涉及到反复的遍历。涉及反复遍历的题目，题目本身虽然不会直接跟你说“你好，我是一道需要反复遍历的题目”，但只要你尝试用常规的思路分析它，你会发现它一定涉及反复遍历；同时，涉及反复遍历的题目，还有一个更明显的特征，就是它们往往会涉及相对复杂的链表操作，比如反转、指定位置的删除等等。
解决这类问题，我们用到的是双指针中的“快慢指针”。快慢指针指的是两个一前一后的指针，两个指针往同一个方向走，只是一个快一个慢。快慢指针严格来说只能有俩，不过实际做题中，可能会出现一前、一中、一后的三个指针，这种超过两个指针的解题方法也叫“多指针法”。
快慢指针+多指针，双管齐下，可以帮助我们解决链表中的大部分复杂操作问题。
# 快慢指针——删除链表的倒数第 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.
