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