有环链表的判断以及入口点计算

题意：给定一个单向链表，求判断该链表是否为带环链表并求出该环的入口点

来源地址：Chasiny

例如下图，一个带环的单向链表

algorithm01.png

方法一：使用辅助结构Map实现

• 思想：用一个map存储所有链表节点的地址，每次存前判断该节点是否在map中，如果存在，则该链表为带环链表并且该节点为环的入口。
• 优点：简单
• 缺点：需要较大的辅助空间

#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;
}

输出结果如下

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

方法二：使用快慢指针

判断是否带环

• 思想：分别用一个快指针跟一个慢指针同时从链表头开始移动，快指针的速度是慢指针的两倍，当快慢指针相遇，则该链表为带环链表。
• 优点：不需要大的辅助空间
• 缺点：比较复杂

判断带环的步骤

algorithm03.png
algorithm04.png
algorithm05.png
algorithm06.png
algorithm07.png
algorithm08.png
algorithm09.png
algorithm10.png
algorithm11.png
algorithm12.png
algorithm13.png

源码实现

判断环的入口：分别用两个指针，一个在快慢指针相遇的地方开始移动，一个从链表的头节点开始移动，当这两个指针相遇时，改节点就是环的入口点

证明：

• 设从头节点到环入口的距离为L，环的入口按链表顺序到快慢指针相遇的节点的距离为M，快慢指针相遇的节点按链表顺序到环的入口的距离为K，环的周长为P，即P - M = L，如下图所示

  
  algorithm02.png

快指针的速度为慢指针的两倍，即

• S(快)=S(慢)*2

由于到两个指针相遇的地点时，快指针比慢指针多走的路程是环的周长的整数倍（快指针追赶慢指针，所以快指针至少比慢指针多走一环的距离），即

• 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

因此从相遇节点按照链表顺序移动L，停下来的位置就是环的入口点

求环的入口的步骤

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;
}

结果是

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