判断一个单链表是否存在环的解法如下：

1.遍历链表，将链表的节点存入hash表内，若遍历到后面的节点已存在hash表内，说明有环。时间：O(n) 空间：O(n)

2.反转链表，时间：O(n) 空间：O(1)，使用3个指针：pNext、pPrev、pCur。这种方法有副作用，就是若存在环的话，无法还原到链表原始状态。（弃用）

3.快慢指针法，时间：O(n) 空间：O(1)。

问题1：快慢指针何时相遇，是否回转几十圈，才相遇呢？

证明1：设环长为L，slow指针第一次进入环内，fast指针在前方的a节点处（0<a<L）,经过x次移动后两个指针相遇。那么即有：

0+x = (a+2x)(mod L) => 0= a+x(mod L) 两边同时减去x

就是说a+x对L求余应该是0，即a+x=0,L,2L……这一系列的解取最小的那个。

得出x=L-a，就是说slow指针进入环后向前移动L-a个位，fast指针向前移动了2L-2a个位，如下图所示：

问题2：如何求前面的子链长度呢？（即环入口点）

证明2：假设在fast与slow第一次相遇是，slow总共走了n步，fast走了2n步。

slow的路径为：n=p+x，x为相遇点到环入口的距离。

fast的路径为：2n=p+x+k*L

可以看出slow到达相遇点后再走n步，还是回到相遇点（p+x）。

将fast置到起点，步长为1，经过n步，也会到达相遇点。这个过程中只有前p步的路径不同，所以当slow与fast再次重合是必然在环入口点上。

下面附上代码：

#include 
     
      using namespace std;struct node{    int value;    node* next;    node(node *p=NULL)    {        value=0;        next=p;    }    node(const int v,node *p=NULL)    {        value=v;        next=p;    }};node* detectLinkListLoop(node *first){    node *fast,*slow;    fast=slow=first;    while(fast && fast->next)    {        slow=slow->next;        fast=fast->next->next;        if (fast == slow)            break;    }    return !(fast == NULL || fast->next == NULL);}node* FindLoopPort(node *head){    node *slow = head, *fast = head;    while ( fast && fast->next )     {        slow = slow->next;        fast = fast->next->next;        if ( slow == fast ) break;    }    if (fast == NULL || fast->next == NULL)        return NULL;    slow = head;    while (slow != fast)    {        slow = slow->next;        fast = fast->next;    }    return slow;}void main(){    node* A=new node(1);    node* B=new node(2);    node* C=new node(3);    node* D=new node(4);    node* E=new node(5);    node* F=new node(6);    node* G=new node(7);    node* H=new node(8);    A->next=B;    B->next=C;    C->next=D;    D->next=E;    E->next=F;    F->next=G;    G->next=H;    H->next=C;    node* first=A;    cout<
      
       <
      
     

感谢两位gocalf、xudacheng06博主的指导，参考文章：