转：单链表有环判断及其起始位置定位

转载至：https://wenku.baidu.com/view/eb0c210af90f76c660371ad7.html

判断一个单链表是否有环的最简便的方法就是追逐法。设置两个指针p和q指向链表的头结点，然后循环移动两个指针，p指针每次移动一个节点，即一步，q指针每次移动两步，如果该单链表存在环，那么两个指针总会在某个位置相遇。因为快指针和慢指针的速度差为1，看成快指针在追慢指针每移动一步两者距离减1，而这个环的最小划分单位就是1，所以显然会相遇。如果无环，则q会率先指向NULL。具体的过程如图所示：

如何找环的入口点：

　　如图3所示，p每次走一步，q每次走两步，q的速度是p的两倍。假设链表的长度为L+S，其中L是链表起点到环起点的距离，S是环的长度，假设快指针和慢指针在环内相遇的时候，慢指针在环内已经走了x步，总共走了y步，那么快指针总共走了2y步。设相遇时快指针在环内已经走了n圈，则：

　　　　　　　　　　　　　　　　　　2y=y+Sn

　　得y=Sn,y是慢指针所走过的总步数，它由链表起点到环起点的距离L和p在环内走的步数组成：

　　　　　　　　　　　　　　　　　　y=L+x

　　变形得：L+x=nS=(n-1)S+S

　　得：L=（n-1)S+S-x。其中S-x相当于慢指针从相遇点继续走到环入口的距离，因此将两个指针设置为慢指针，一个从链表头开始走，一个从相遇点开始走。环内的指针走过S-x距离，再走n-1圈。两指针就会在环入口相遇。

C++代码：

1、链表有环判断：

 1 bool isCircleLink(Node* head){
 2     if(head==nullptr)
 3         return false;
 4     Node *p,*q;
 5     p=q=head;
 6     while(q!=nullptr && q->next!=nullptr){
 7         p=p->next;
 8         q=q->next->next;
 9         if(q==p)
10             break;
11     }
12     if(q==p && p!=nullptr)
13         return true;
14     return false;
15 }

2、寻找链表环起始位置

 1 Node circleStar(Node * head){
 2     if(head==nullptr)
 3         return false;
 4     Node* p,*q;
 5     p=q=head;
 6     while(q!=nullptr && q->next!=nullptr){
 7         p=p->next;
 8         q=q->next->next;
 9         if(p==q)
10             break;
11     }
12     if(p==q && p!=nullptr){
13         q=head;
14         while(p!=q){
15             p=p->next;
16             q=q->next;
17         }
18         return p;
19     }
20     else
21         return nullptr;
22 }