快慢指针的妙用
快慢指针是双指针的一种典型用法，通常控制两个指针以不同的速度移动来解决问题。采用快慢指针解决问题往往都很巧妙。本文我们通过分析几个例子来学习快慢指针的用法，并分析其本质，最终达到方便记忆、灵活使用的目的。
接下来我们先看四个例子：判断链表是否有环、寻找链表中环的入口、寻找链表的中间结点、寻找链表的倒数第 n 个结点。
判断链表是否有环
题目（来源Leetcode）
“给你一个链表的头结点 head ，判断链表中是否有环。
如果链表中有某个结点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。”
环形链表：leetcode-cn.com/problems/li…
分析
这道题有两种常见解法：1. 哈希表 2. 快慢指针。我们主要分析快慢指针的解法：
我们定义两个指针：一个移动的慢叫慢指针，一个移动的快叫快指针。慢指针在链表中一次移动一个结点，快指针在链表中一次移动两个结点，如果两个指针最终相遇了，说明有环；如果快指针顺利到达了链表的终点说明没有环。
相遇：快指针 = 慢指针；到达终点：快指针的下一个结点为Null。
要想理解这个解决办法需要先了解：Floyd 判圈算法。
Floyd 判圈算法又称为龟兔赛跑算法（Tortoise and Hare Algorithm）。乌龟跑得慢、兔子跑得快。乌龟和兔子在赛跑，如果存在环的话，兔子必然会追上乌龟（乌龟被套圈了）。
我们把乌龟比作慢指针、兔子比作快指针同时在链表中移动。跑步和指针移动不太相同的是，跑步的路程是连续的，快指针一次移动两个结点是不连续的。又反过来想一下如果链表中存在环，那最小的环也需要两个结点，所以对于是否有环来说快指针一次移动两个结点也是不会错过任何一个环的。而且环的结点不管是奇数还是偶数个，快指针也最终会和慢指针在某个结点重合。
答案
基于上面的分析我们给出代码如下：
func hasCycle(head *ListNode) bool {
if head == nil || head.Next == nil { // 如果链表有0个或者1个结点，则链表不存在环
return false
}
slowPoint, fastPoint := head, head.Next // 定义快慢指针
for fastPoint != slowPoint { // 如果快慢指针相等则结束循环，证明有环
if fastPoint == nil || fastPoint.Next == nil { // 如果快指针到达终点或者终点前的倒数第一个结点，说明没有环
return false
}
slowPoint = slowPoint.Next
fastPoint = fastPoint.Next.Next
}
return true
}
寻找链表中环的入口
题目（来源Leetcode）
“给定一个链表的头结点 head ，返回链表开始入环的第一个结点。 如果链表无环，则返回 null。
如果链表中有某个结点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。”
环形链表 II：leetcode-cn.com/problems/li…
分析
这道题和上题一样，通常有哈希表、快慢指针两种解法。我们主要分析快慢指针的解法：
我们定义两个指针：一个移动的慢叫慢指针，一个移动的快叫快指针。慢指针在链表中一次移动一个结点，快指针在链表中一次移动两个结点，如果两个指针最终相遇了，说明有环；如果快指针顺利到达了链表的终点说明没有环。
当有环存在时，我们假设快慢指针在 D 点相遇。a 代表入环之前的长度，b 代表慢指针进入环后又走了b的长度，c 代表环余下的长度。指针的指向是圆的顺时针方向。
- 如果快指针和慢指针在 D 点相遇，此时快指针比慢指针多走了 n 圈，也就是 n*(b+c) 的长度。
- 此时快指针走过的距离是 a+n*(b+c)+b，慢指针走过的距离是 a+b。
- 因为快指针每次走两步，慢指针每次走一步，所以快指针走过的距离永远是慢指针的两倍，所以 a+n* (b+c)+b=2(a+b)*
- 上述公式可以推导出a = (n-1)*(b+c)+c，也就是a的长度是恰好是 n-1 圈环的长度加上从 D 点到相遇点的距离。
根据上面的推论，当快慢指针相遇之后，我们再申请一个指针从链表的头部开始，每次移动一个结点，同时慢指针一次移动一个结点，这两个指针最终的相遇点就是环的入口点。
答案
func detectCycle(head *ListNode) *ListNode {
slowPoint, fastPoint := head, head
for fastPoint != nil && fastPoint.Next != nil { // 如果快指针到达终点或者终点前的倒数第一个结点，说明没有环。
slowPoint = slowPoint.Next
fastPoint = fastPoint.Next.Next
if fastPoint == slowPoint { // 如果快慢指针相等，说明有环，后面开始寻找环的入口。
delectPoint := head
for delectPoint != slowPoint { // 慢指针和从头开始的delectPoint指针相等，则说明当前结点就是环的入口。
delectPoint = delectPoint.Next
slowPoint = slowPoint.Next
}
return delectPoint
}
}
return nil
}
寻找链表的中间结点
题目（来源Leetcode）
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
链表的中间结点：leetcode-cn.com/problems/mi…
分析
这道题有多种解法，但是快慢指针的解法十分巧妙。我们定义两个指针：一个移动的慢叫慢指针，一个移动的快叫快指针。慢指针在链表中一次移动一个结点，快指针在链表中一次移动两个结点。因为快指针移动的距离始终是慢指针的两倍，所以当快指针移动到链表尾部时，慢指针刚好在链表中间位置。
答案
func middleNode(head *ListNode) *ListNode {
slowPoint, fastPoint := head, head
for fastPoint!= nil && fastPoint.Next != nil{
slowPoint = slowPoint.Next
fastPoint = fastPoint.Next.Next
}
return slowPoint
}
寻找链表的倒数第 N 个结点
题目
给你一个链表，找到链表的倒数第 n 个结点并返回。
分析
这道题有多种解法，但是快慢指针的解法十分巧妙。我们定义两个指针：两个指针每次移动一个结点。我们让其中一个指针先移动 n 个结点，先移动的这个指针我们叫它快指针，另外一个叫慢指针。然后两个指针同时移动。因为移动速度相同所以两个指针之间的距离始终是 n ，当快指针到达链表尾部时，慢指针刚好指向了链表的倒数第 n 个结点。
这里叫“快慢指针”有点牵强，感觉叫前后指针更合适，不过为了方便记忆就先归为快慢指针吧。
答案
func findNthFromEnd(head *ListNode, n int) *ListNode {
fastPoint,slowPoint := node,node
for i:=0; i<n+1; i++{
fastPoint = fastPoint.Next
}
for fastPoint != nil {
fastPoint= fastPoint.Next
slowPoint = slowPoint.Next
}
return slowPoint
}
总结
本文我们介绍了快慢指针的常见用法：
- 利用 Floyd 判圈算法找环。
- 利用 Floyd 判圈算法找环的入口。
- 寻找链表的中间结点。
- 寻找链表的倒数第 n 个结点。
在 Floyd 判圈算法中，把判断环的问题抽象成两个指针围绕环运动最终会相遇的问题，通过环形跑道这个生动场景解决了问题；在寻找链表中间节点时，利用两个指针的速度差，使一个指针运动的距离始终是另外一个指针的一半，用指针的速度、路程解决了问题；在寻找链表倒数第 n 个节点时，让相同速度的两个指针始终保持 n 的相对距离，把链表问题抽象成了距离问题。
这几种方法都是把算法问题抽象成了两个指针的距离、速度问题，最终通过数学公式推导得出结论。推而广之，我们以后遇到链表的相关问题也可以采用类似的方式去抽象问题，推导解决办法。
作者：一行舟
链接：https://juejin.cn/post/7074945262292041758
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
