題意：給定一個(gè)單向鏈表，求判斷該鏈表是否為帶環(huán)鏈表并求出該環(huán)的入口點(diǎn)
例如下圖凡简，一個(gè)帶環(huán)的單向鏈表
algorithm01.png
方法一：使用輔助結(jié)構(gòu)Map實(shí)現(xiàn)
- 思想：用一個(gè)map存儲(chǔ)所有鏈表節(jié)點(diǎn)的地址，每次存前判斷該節(jié)點(diǎn)是否在map中精肃，如果存在，則該鏈表為帶環(huán)鏈表并且該節(jié)點(diǎn)為環(huán)的入口帜乞。
- 優(yōu)點(diǎn)：簡(jiǎn)單
- 缺點(diǎn)：需要較大的輔助空間
#include <iostream>
#include <map>
using namespace std;
struct Node{
int Val;
Node* next;
};
Node* Init(){
int nodeData[]={1,2,3,4,5,6,7,8,9,10,11,12};
Node* node[12];
for(int i=0;i<sizeof(node)/sizeof(Node*);i++){
node[i]=new Node;
node[i]->Val=nodeData[i];
cout<<"create node "<<node[i]->Val<<endl;
}
for(int i=0;i<sizeof(node)/sizeof(Node*)-1;i++){
node[i]->next=node[i+1];
}
node[sizeof(node)/sizeof(Node*)-1]->next=node[7];
return node[0];
}
int main(){
Node* head=Init();
map<Node*,int> nodeMap;
while(head){
if(nodeMap[head]==0){
nodeMap[head]=1;
}else{
cout<<"this is a ring list, entrance is: "<<head->Val<<endl;
break;
}
head=head->next;
}
return 0;
}
輸出結(jié)果如下
create node 1
create node 2
create node 3
create node 4
create node 5
create node 6
create node 7
create node 8
create node 9
create node 10
create node 11
create node 12
this is a ring list, entrance is: 8
方法二：使用快慢指針
判斷是否帶環(huán)
- 思想：分別用一個(gè)快指針跟一個(gè)慢指針同時(shí)從鏈表頭開(kāi)始移動(dòng)司抱，快指針的速度是慢指針的兩倍，當(dāng)快慢指針相遇黎烈，則該鏈表為帶環(huán)鏈表习柠。
- 優(yōu)點(diǎn)：不需要大的輔助空間
- 缺點(diǎn)：比較復(fù)雜
判斷帶環(huán)的步驟
algorithm03.png
algorithm04.png
algorithm05.png
algorithm06.png
algorithm07.png
algorithm08.png
algorithm09.png
algorithm10.png
algorithm11.png
algorithm12.png
algorithm13.png
源碼實(shí)現(xiàn)
判斷環(huán)的入口：分別用兩個(gè)指針匀谣，一個(gè)在快慢指針相遇的地方開(kāi)始移動(dòng)，一個(gè)從鏈表的頭節(jié)點(diǎn)開(kāi)始移動(dòng)资溃，當(dāng)這兩個(gè)指針相遇時(shí)武翎，改節(jié)點(diǎn)就是環(huán)的入口點(diǎn)
證明：
-
設(shè)從頭節(jié)點(diǎn)到環(huán)入口的距離為L(zhǎng)，環(huán)的入口按鏈表順序到快慢指針相遇的節(jié)點(diǎn)的距離為M溶锭，快慢指針相遇的節(jié)點(diǎn)按鏈表順序到環(huán)的入口的距離為K宝恶，環(huán)的周長(zhǎng)為P，即P - M = L趴捅，如下圖所示
algorithm02.png
快指針的速度為慢指針的兩倍垫毙，即
- S(快)=S(慢)*2
由于到兩個(gè)指針相遇的地點(diǎn)時(shí)，快指針比慢指針多走的路程是環(huán)的周長(zhǎng)的整數(shù)倍（快指針追趕慢指針拱绑，所以快指針至少比慢指針多走一環(huán)的距離）综芥，即
- S(快) - S(慢) = n1 * P (n1 >= 1)
- 得 S(慢) = n1 * P (n1 >= 1)
- 又有S(慢) = L + M + n2 * P (n2 >= 0)
- 得 n1 * P = L + M + n2 * P (n1 >= 1 , n2 >= 0)
- 得 (n1 - n2) * P = L + M
- (n1 - n2) * P = L + (P - K)
- (n1 - n2 -1) * P + K = L
因此從相遇節(jié)點(diǎn)按照鏈表順序移動(dòng)L，停下來(lái)的位置就是環(huán)的入口點(diǎn)
求環(huán)的入口的步驟
algorithm14.png
algorithm15.png
algorithm16.png
algorithm17.png
algorithm18.png
algorithm19.png
algorithm20.png
algorithm21.png
快慢指針代碼樣例
#include <iostream>
#include <map>
using namespace std;
struct Node{
int Val;
Node* next;
};
Node* Init(){
int nodeData[]={1,2,3,4,5,6,7,8,9,10,11,12};
Node* node[12];
for(int i=0;i<sizeof(node)/sizeof(Node*);i++){
node[i]=new Node;
node[i]->Val=nodeData[i];
cout<<"create node "<<node[i]->Val<<endl;
}
for(int i=0;i<sizeof(node)/sizeof(Node*)-1;i++){
node[i]->next=node[i+1];
}
node[sizeof(node)/sizeof(Node*)-1]->next=node[7];
return node[0];
}
int main(){
Node* head=Init();
Node* qPos=head;
Node* sPos=head;
while(qPos){
sPos=sPos->next;
if(!qPos->next){
cout<<"this is not a ring list\n";
break;
}
qPos=qPos->next->next;
if(sPos==qPos){
cout<<"this is a ring list\n";
break;
}
}
Node* tPos=head;
while(true){
tPos=tPos->next;
sPos=sPos->next;
if(tPos==sPos){
cout<<"entrance is: "<<sPos->Val<<endl;
break;
}
}
return 0;
}
結(jié)果是
create node 1
create node 2
create node 3
create node 4
create node 5
create node 6
create node 7
create node 8
create node 9
create node 10
create node 11
create node 12
this is a ring list
entrance is: 8
