思路：如果开始有两个指针指向头结点，一个走的快，一个走的慢，如果有环的话，最终经过若干步，快的指针总会超过慢的指针一圈从而相遇。

　　如何计算环的长度呢？可以第一次相遇时开始计数，第二次相遇时停止计数。

　　如何判断环的入口点？碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。

　　当fast与slow相遇时，show肯定没有走完链表，而fast已经在还里走了n（n>= 1）圈。假设slow走了s步，那么fast走了2s步。fast的步数还等于s走的加上环里转的n圈，所以

有：2s = s + nr。因此，s = nr。   　

　　设整个链表长为L，入口据相遇点X，起点到入口的距离为a。因为slow指针并没有走完一圈，所以：a + x = s，带入第一步的结果，有：a + x =

nr = (n-1)r + r = (n-1)r + L - a；即：a = (n-1)r + L -a -x;

　　这说明：从头结点到入口的距离，等于转了(n-1)圈以后，相遇点到入口的距离。因此，我们可以在链表头、相遇点各设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

 

判断是否有环

 

bool hasCycle(ListNode *head) {        ListNode *fast(head), *slow(head);        while(fast && fast->next)        {            fast = fast->next->next;            slow = slow->next;            if(fast == slow)                return true;        }        return false;    }

 

 

计算环的长度

int loopLength(ListNode *head){    if(hasCycle(head) == false)        return 0;    ListNode *fast = head;    ListNode *slow = head;    int length = 0;    bool begin = false;    bool again = false;    while( fast != NULL && fast->next != NULL)    {        fast = fast->next->next;        slow = slow->next;        //超两圈后停止计数，挑出循环        if(fast == slow && again== true)            break;        //超一圈后开始计数        if(fast == slow && again == false)        {                        begin = true;            again= true;        }        //计数        if(begin == true)            ++length;            }    return length;}

 

//求环的入口结点

ListNode* findLoopEntrance(ListNode *head){    ListNode *fast = head;    ListNode * slow = head;    while( fast != NULL && fast->next != NULL)    {        fast = fast->next->next;        slow = slow->next;        //如果有环，则fast会超过slow一圈        if(fast == slow)        {            break;        }    }    if(fast == NULL || fast->next == NULL)        return NULL;    slow = head;    while(slow != fast)    {        slow = slow->next;        fast = fast->next;    }    return slow;}