浅谈判圈算法
在计算机科学中，循环检测算法可用于判断状态机中是否存在循环、链表是否存在环等问题
Floyd判圈算法
判断是否有环
该算法判断是否存在环的基本原理是分别使用快、慢指针进行遍历。其中，快指针每次走2步、慢指针每次走1步。如果两个指针相遇了，则说明存在环；反之，则不存在环
计算环的长度
当存在环时如何计算环的长度呢？其实也很简单。因为判断是否存在环的过程中，当快、慢指针相遇则说明这两个指针一定位于环当中了。故此时，只需使用其中任意一个指针按照每次走1步对环遍历一圈、进行计数即可
计算环的入口
这里令起始处为A、环的入口处为B，在判断是否有环阶段时快慢相遇之处为C。并记AB长度为a、记BC长度为b、环的长度为r。且在判断是否有环过程中，快指针每次走2步、慢指针每次走1步。则快、慢指针相遇时，快指针走过的长度是慢指针走过长度的2倍
此时不难看出，当快、慢指针相遇时，快、慢指针走过的长度均是环长度的整数倍。故如果期望找到环的入口位置，即B处。则只需在两个指针相遇之时，将其中任意一个指针放置到起始处A，而另一个指针依然位于相遇处C。然后两个指针按照每次均走1步的速度向前走，当二者再次相遇之时，即是B处
原因在于，对于相遇后继续往前走的指针而言，由于其已经走过了若干圈环的长度，此时只需再走a步即可到达环的入口。这个地方换个角度想会更容易理解，如果该指针先走a步再走若干圈环的长度，其必然位于环的入口处；而对于相遇后从起始处A开始走的指针而言，其显然走a步后，必然也会位于环的入口处。故此时两个指针第二次相遇之时，说明他们均已经走完a步。即到达环的入口处
Brent判圈算法
Brent判圈算法相比较于Floyd判圈算法来说，其重点在于提高了判断是否有环的时间效率。该算法并没有解决计算环的长度、找出环的入口这两个问题。具体地，该算法同样会使用两个指针：快、慢指针。当两个指针相遇则说明存在环。具体地，快指针每次始终只会走1步。只不过，第1轮时快指针累计最多只能走2步，第2轮时快指针累计最多只能走4步，第3轮时快指针累计最多只能走8步,以此类推。而慢指针则是在每一轮结束后，直接移动到快指针的位置处
实践
判断是否有环
学习过程中要善于理论联系实际。故在介绍完Floyd判圈算法、Brent判圈算法的基本原理后，现在我们来进行实践。这里以LeetCode的第141题——环形链表 为例
给你一个链表的头节点head，判断链表中是否有环 如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。如果链表中存在环，则返回 true。否则，返回 false
示例 1：
输入：head = [3,2,0,-4]
输出：true
解释：链表中有一个环，其尾部连接到第二个节点
示例 2：
输入：head = [1,2]
输出：true
解释：链表中有一个环，其尾部连接到第一个节点
示例 3：
输入：head = [1]
输出：false
解释：链表中没有环
则基于Floyd判圈算法版本的实现如下所示
/**
* Floyd Algo
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = slow;
while ( fast!=null && fast.next!=null ) {
slow = slow.next;
fast = fast.next.next;
if( slow==fast ) {
return true;
}
}
return false;
}
}
则基于Brent判圈算法版本的实现如下所示
/**
* Brent Algo
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = slow;
// 快指针每轮过程中最多走几步
int limit = 2;
// 记录快指针在每轮过程中走的步数
int step = 0;
while ( fast!=null && fast.next!=null ) {
// 快指针每次走1步
fast = fast.next;
step++;
// 判断快、慢指针是否相遇, 即是否存在环
if( fast == slow ) {
return true;
}
// 开启新一轮的同时, limit变为原来的2倍, 同时将慢指针移动到快指针的位置上
if( step==limit ) {
step = 0;
limit = limit * 2;
slow = fast;
}
}
return false;
}
}
计算环的入口
学习过程中要善于理论联系实际。故在介绍完Floyd判圈算法、Brent判圈算法的基本原理后，现在我们来进行实践。这里以LeetCode的第141题——环形链表 II 为例
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。不允许修改链表
示例 1：
输入：head = [3,2,0,-4]
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点
示例 2：
输入：head = [1,2]
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点
示例 3：
输入：head = [1]
输出：返回 null
解释：链表中没有环
根据上文对计算环的入口的说明，不难写出以下代码
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode entry = null;
boolean hasCycle = false;
ListNode slow = head;
ListNode fast = head;
while ( fast!=null && fast.next!=null ) {
slow = slow.next;
fast = fast.next.next;
if( slow==fast ) {
// 检测到环
hasCycle = true;
break;
}
}
// 存在环时, 则计算环的入口
if( hasCycle ) {
// 快指针放置到链表开始处
fast = head;
// 快、慢指针每次1步同时移动
while ( true ) {
// 快、慢指针再次相遇, 即为环的入口
if( fast==slow ) {
entry = fast;
break;
}
fast = fast.next;
slow = slow.next;
}
}
return entry;
}
}