判斷連結清單是否有環及環的入口

1.如何判斷是否有環？如果有兩個頭結點指針，一個走的快，一個走的慢，那麼若幹步以後，快的指針總會超過慢的指針一圈。

2.如何計算環的長度？第一次相遇（超一圈）時開始計數，第二次相遇時停止計數。

3.如何判斷環的入口點：碰撞點p到連接配接點的距離=頭指針到連接配接點的距離，是以，分别從碰撞點、頭指針開始走，相遇的那個點就是連接配接點。

為什麼呢？需要一個簡單的計算過程：

（1）當fast與slow相遇時，show肯定沒有走完連結清單，而fast已經在還裡走了n（n>= 1）圈。假設slow走了s步，那麼fast走了2s步。fast的步數還等于s走的加上環裡轉的n圈，是以有：

2s = s + nr。是以，s = nr。

（2）設整個連結清單長為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)圈以後，相遇點到入口的距離。是以，我們可以在連結清單頭、相遇點各設一個指針，每次各走一步，兩個指針必定相遇，且相遇第一點為環入口點。

也許大家有一個問題，就是為什麼“當fast與slow相遇時，show肯定沒有走完連結清單”。這個問題比較坑，我也沒有找到很好的證明。不過大家自己畫幾個試試，會發現的确是這樣。

4.如何判斷兩個連結清單（不帶環）是否相交？将其中的一個連結清單首尾相連，然後判斷另一個連結清單是否帶環即可。這個比較簡單，程式就省略了。

#include <stdio.h>

typedef struct ListNode
{
    int val;
    ListNode *next;
}ListNode,*pNode;



//判斷是否有環
bool isLoop(ListNode *pHead)
{
    ListNode *slow = pHead;
    ListNode *fast= slow->next;
    //如果無環，則fast先走到終點
    //當連結清單長度為奇數時，fast->Next為空
    //當連結清單長度為偶數時，fast為空
    while( fast != NULL && slow != NULL)
    {

        fast = fast->next;
        slow = slow->next;
        //如果有環，則fast會超過slow一圈
        if(fast == slow)
        {
            break;
        }
    }

    if(fast == NULL || slow== NULL  )
        return false;
    else
        return true;
}

//計算環的長度
int loopLength(ListNode *pHead)
{
    if(isLoop(pHead) == false)
        return ;
    ListNode *slow = pHead;
    ListNode *fast = slow->fast;
    int length = ;
    bool begin = false;
    bool agian = false;
    while( fast != NULL && fast->next != NULL)
    {
        fast = fast->next;
        slow = slow->next;
        //超兩圈後停止計數，挑出循環
        if(fast == slow && agian == true)
            break;
        //超一圈後開始計數
        if(fast == slow && agian == false)
        {           
            begin = true;
            agian = true;
        }

        //計數
        if(begin == true)
            ++length;

    }
    return length;
}


//求出環的入口點
Node* findLoopEntrance(ListNode *pHead)
{
    ListNode *slow = pHead;
    ListNode *fast = slow->fast;
    while( fast != NULL && slow!= NULL)
    {

        fast = fast->next;
        slow = slow->next;
        //如果有環，則fast會超過slow一圈
        if(fast == slow)
        {
            break;
        }
    }
    if(fast == NULL || slow == NULL)
        return NULL;
    slow = pHead;
    while(slow != fast)
    {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}