判斷單連結清單是否存在環以及求出環的入口

一、問題描述： 給定一個單連結清單，判斷是否存在環。

求解思路：給兩個速度不一樣的指針，進入一個循環，檢視二者是否相等。

算法代碼：

bool  Is_has_loop(link_list  *head)
{   if(head == NULL)
        return;
    link_list  *fast,*slow;
    fast = slow = head;
    while(fast && fast -> next)
    {
        fast = fast -> next -> next;
        slow = slow -> next;
        if(fast == slow)
        {
            break;
        }
    }
    return !(fast == NULL || fast->next == NULL);
}
           

解法如下： 

定義兩個指針：fast和slow，當fast按照每次2步，slow每次一步的方式走，發現fast和slow重合，确定了單向連結清單有環路了。

二、求環的入口

接下來，讓fast回到連結清單的頭部，重新走，每次步長不是走2了，而是走1，那麼當fast和slow再次相遇的時候，就是環路的入口了。

這點可以證明的：

在fast和lslow第一次相遇的時候，假定slow走了n步驟，環路的入口是在p步的時候經過的，那麼有

slow走的路徑： p+c ＝ n；         c為p1和p2相交點，距離環路入口的距離

fast走的路徑： p+c+k*L = 2*N；   L為環路的周長，k是整數

顯然，如果從p+c點開始，p1再走n步驟的話，還可以回到p+c這個點

同時fast從頭開始走的話，經過n步，也會達到p+c這點

顯然在這個步驟當中slow和fast隻有前p步驟走的路徑不同，是以當slow和slow再次重合的時候，必然是在連結清單的環路入口點上。

找到環的入口代碼實作：

link_list *  FindLoopPort(link_list  * head)
{
    link_list  * 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;
    fast  =  head;
    while  (slow  !=  fast)
    {
    slow  =  slow -> next;
    fast  =  fast -> next;
    }
    return  slow;
}