淺談判圈算法
在計算機科學(xué)中，循環(huán)檢測算法可用于判斷狀態(tài)機中是否存在循環(huán)、鏈表是否存在環(huán)等問題
Floyd判圈算法
判斷是否有環(huán)
該算法判斷是否存在環(huán)的基本原理是分別使用快、慢指針進(jìn)行遍歷。其中，快指針每次走2步、慢指針每次走1步。如果兩個指針相遇了，則說明存在環(huán)；反之，則不存在環(huán)
計算環(huán)的長度
當(dāng)存在環(huán)時如何計算環(huán)的長度呢？其實也很簡單。因為判斷是否存在環(huán)的過程中，當(dāng)快、慢指針相遇則說明這兩個指針一定位于環(huán)當(dāng)中了。故此時，只需使用其中任意一個指針按照每次走1步對環(huán)遍歷一圈、進(jìn)行計數(shù)即可
計算環(huán)的入口
這里令起始處為A、環(huán)的入口處為B，在判斷是否有環(huán)階段時快慢相遇之處為C。并記AB長度為a、記BC長度為b、環(huán)的長度為r。且在判斷是否有環(huán)過程中，快指針每次走2步、慢指針每次走1步。則快、慢指針相遇時，快指針走過的長度是慢指針走過長度的2倍
此時不難看出，當(dāng)快、慢指針相遇時，快、慢指針走過的長度均是環(huán)長度的整數(shù)倍。故如果期望找到環(huán)的入口位置，即B處。則只需在兩個指針相遇之時，將其中任意一個指針放置到起始處A，而另一個指針依然位于相遇處C。然后兩個指針按照每次均走1步的速度向前走，當(dāng)二者再次相遇之時，即是B處
原因在于，對于相遇后繼續(xù)往前走的指針而言，由于其已經(jīng)走過了若干圈環(huán)的長度，此時只需再走a步即可到達(dá)環(huán)的入口。這個地方換個角度想會更容易理解，如果該指針先走a步再走若干圈環(huán)的長度，其必然位于環(huán)的入口處；而對于相遇后從起始處A開始走的指針而言，其顯然走a步后，必然也會位于環(huán)的入口處。故此時兩個指針第二次相遇之時，說明他們均已經(jīng)走完a步。即到達(dá)環(huán)的入口處
Brent判圈算法
Brent判圈算法相比較于Floyd判圈算法來說，其重點在于提高了判斷是否有環(huán)的時間效率。該算法并沒有解決計算環(huán)的長度、找出環(huán)的入口這兩個問題。具體地，該算法同樣會使用兩個指針：快、慢指針。當(dāng)兩個指針相遇則說明存在環(huán)。具體地，快指針每次始終只會走1步。只不過，第1輪時快指針累計最多只能走2步，第2輪時快指針累計最多只能走4步，第3輪時快指針累計最多只能走8步,以此類推。而慢指針則是在每一輪結(jié)束后，直接移動到快指針的位置處
實踐
判斷是否有環(huán)
學(xué)習(xí)過程中要善于理論聯(lián)系實際。故在介紹完Floyd判圈算法、Brent判圈算法的基本原理后，現(xiàn)在我們來進(jìn)行實踐。這里以LeetCode的第141題——環(huán)形鏈表 為例
給你一個鏈表的頭節(jié)點head，判斷鏈表中是否有環(huán) 如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤next指針再次到達(dá)，則鏈表中存在環(huán)。如果鏈表中存在環(huán)，則返回 true。否則，返回 false
示例 1：
輸入：head = [3,2,0,-4]
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點
示例 2：
輸入：head = [1,2]
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點
示例 3：
輸入：head = [1]
輸出：false
解釋：鏈表中沒有環(huán)
則基于Floyd判圈算法版本的實現(xiàn)如下所示
/**
* 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判圈算法版本的實現(xiàn)如下所示
/**
* Brent Algo
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = slow;
// 快指針每輪過程中最多走幾步
int limit = 2;
// 記錄快指針在每輪過程中走的步數(shù)
int step = 0;
while ( fast!=null && fast.next!=null ) {
// 快指針每次走1步
fast = fast.next;
step++;
// 判斷快、慢指針是否相遇, 即是否存在環(huán)
if( fast == slow ) {
return true;
}
// 開啟新一輪的同時, limit變?yōu)樵瓉淼?倍, 同時將慢指針移動到快指針的位置上
if( step==limit ) {
step = 0;
limit = limit * 2;
slow = fast;
}
}
return false;
}
}
計算環(huán)的入口
學(xué)習(xí)過程中要善于理論聯(lián)系實際。故在介紹完Floyd判圈算法、Brent判圈算法的基本原理后，現(xiàn)在我們來進(jìn)行實踐。這里以LeetCode的第141題——環(huán)形鏈表 II 為例
給定一個鏈表的頭節(jié)點 head ，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。不允許修改鏈表
示例 1：
輸入：head = [3,2,0,-4]
輸出：返回索引為 1 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點
示例 2：
輸入：head = [1,2]
輸出：返回索引為 0 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點
示例 3：
輸入：head = [1]
輸出：返回 null
解釋：鏈表中沒有環(huán)
根據(jù)上文對計算環(huán)的入口的說明，不難寫出以下代碼
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 ) {
// 檢測到環(huán)
hasCycle = true;
break;
}
}
// 存在環(huán)時, 則計算環(huán)的入口
if( hasCycle ) {
// 快指針放置到鏈表開始處
fast = head;
// 快、慢指針每次1步同時移動
while ( true ) {
// 快、慢指針再次相遇, 即為環(huán)的入口
if( fast==slow ) {
entry = fast;
break;
}
fast = fast.next;
slow = slow.next;
}
}
return entry;
}
}