題意：給定一個單向鏈表，求判斷該鏈表是否為帶環(huán)鏈表并求出該環(huán)的入口點
例如下圖，一個帶環(huán)的單向鏈表
algorithm01.png
方法一：使用輔助結(jié)構(gòu)Map實現(xiàn)
- 思想：用一個map存儲所有鏈表節(jié)點的地址，每次存前判斷該節(jié)點是否在map中，如果存在，則該鏈表為帶環(huán)鏈表并且該節(jié)點為環(huán)的入口。
- 優(yōu)點：簡單
- 缺點：需要較大的輔助空間
#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)
- 思想：分別用一個快指針跟一個慢指針同時從鏈表頭開始移動，快指針的速度是慢指針的兩倍，當快慢指針相遇，則該鏈表為帶環(huán)鏈表。
- 優(yōu)點：不需要大的輔助空間
- 缺點：比較復雜
判斷帶環(huán)的步驟
algorithm03.png
algorithm04.png
algorithm05.png
algorithm06.png
algorithm07.png
algorithm08.png
algorithm09.png
algorithm10.png
algorithm11.png
algorithm12.png
algorithm13.png
源碼實現(xiàn)
判斷環(huán)的入口：分別用兩個指針，一個在快慢指針相遇的地方開始移動，一個從鏈表的頭節(jié)點開始移動，當這兩個指針相遇時，改節(jié)點就是環(huán)的入口點
證明：
-
設(shè)從頭節(jié)點到環(huán)入口的距離為L，環(huán)的入口按鏈表順序到快慢指針相遇的節(jié)點的距離為M，快慢指針相遇的節(jié)點按鏈表順序到環(huán)的入口的距離為K，環(huán)的周長為P，即P - M = L，如下圖所示
algorithm02.png
快指針的速度為慢指針的兩倍，即
- S(快)=S(慢)*2
由于到兩個指針相遇的地點時，快指針比慢指針多走的路程是環(huán)的周長的整數(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é)點按照鏈表順序移動L，停下來的位置就是環(huá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
