摘要：由于要比移動(dòng)的快，如果有環(huán)，一定會先進(jìn)入環(huán)，而后進(jìn)入環(huán)。現(xiàn)在問題就簡單了，由于移動(dòng)的距離永遠(yuǎn)是的一般，因此當(dāng)遍歷玩整個(gè)環(huán)長度個(gè)節(jié)點(diǎn)的時(shí)候正好遍歷了個(gè)節(jié)點(diǎn)，也就是說，此時(shí)正好指向距離最遠(yuǎn)的點(diǎn)。

首先，關(guān)于單鏈表中的環(huán)，一般涉及到以下問題：

1.給一個(gè)單鏈表，判斷其中是否有環(huán)的存在；

2.如果存在環(huán)，找出環(huán)的入口點(diǎn)；

3.如果存在環(huán)，求出環(huán)上節(jié)點(diǎn)的個(gè)數(shù)；

4.如果存在環(huán)，求出鏈表的長度；

5.如果存在環(huán)，求出環(huán)上距離任意一個(gè)節(jié)點(diǎn)最遠(yuǎn)的點(diǎn)（對面節(jié)點(diǎn)）；

6.（擴(kuò)展）如何判斷兩個(gè)無環(huán)鏈表是否相交；

7.（擴(kuò)展）如果相交，求出第一個(gè)相交的節(jié)點(diǎn)；

下面，我將針對上面這七個(gè)問題一一給出解釋和相應(yīng)的代碼。

1.判斷時(shí)候有環(huán)（鏈表頭指針為head）

對于這個(gè)問題我們可以采用“快慢指針”的方法。就是有兩個(gè)指針fast和slow，開始的時(shí)候兩個(gè)指針都指向鏈表頭head，然后在每一步

操作中slow向前走一步即：slow = slow->next，而fast每一步向前兩步即：fast = fast->next->next。

由于fast要比slow移動(dòng)的快，如果有環(huán)，fast一定會先進(jìn)入環(huán)，而slow后進(jìn)入環(huán)。當(dāng)兩個(gè)指針都進(jìn)入環(huán)之后，經(jīng)過一定步的操作之后

二者一定能夠在環(huán)上相遇，并且此時(shí)slow還沒有繞環(huán)一圈，也就是說一定是在slow走完第一圈之前相遇。證明可以看下圖：

當(dāng)slow剛進(jìn)入環(huán)時(shí)每個(gè)指針可能處于上面的情況，接下來slow和fast分別向前走即：

if (slow != NULL && fast->next != NULL)  
{  
         slow = slow -> next ;  
         fast = fast -> next -> next ;  
} 

也就是說，slow每次向前走一步，fast向前追了兩步，因此每一步操作后fast到slow的距離縮短了1步，這樣繼續(xù)下去就會使得
兩者之間的距離逐漸縮小：...、5、4、3、2、1、0 -> 相遇。又因?yàn)樵谕粋€(gè)環(huán)中fast和slow之間的距離不會大于換的長度，因此

到二者相遇的時(shí)候slow一定還沒有走完一周（或者正好走完以后，這種情況出現(xiàn)在開始的時(shí)候fast和slow都在環(huán)的入口處）。

問題1是否存在環(huán)的解答

typedef struct node{  
    char data ;  
    node * next ;  
}Node;  
bool exitLoop(Node *head)  
{  
    Node *fast, *slow ;  
    slow = fast = head ;  
  
    while (slow != NULL && fast -> next != NULL)  
    {  
        slow = slow -> next ;  
        fast = fast -> next -> next ;  
        if (slow == fast)  
            return true ;  
    }  
    return false ;  
}

問題2 環(huán)的入口點(diǎn)：

從上面的分析知道，當(dāng)fast和slow相遇時(shí)，slow還沒有走完鏈表，假設(shè)fast已經(jīng)在環(huán)內(nèi)循環(huán)了n(1<= n)圈。假設(shè)slow走了s步，則fast走了2s步，又由于
fast走過的步數(shù) = s + n*r（s + 在環(huán)上多走的n圈），則有下面的等式：
2s = s + n ? r；（1）
=> s = n*r；（2）

如果假設(shè)整個(gè)鏈表的長度是L，入口和相遇點(diǎn)的距離是x（如上圖所示），起點(diǎn)到入口點(diǎn)的距離是a(如上圖所示)，則有：
a + x = s = n * r; (3) ?由（2）推出
a + x = (n - 1) r + r ?= (n - 1) r + (L - a) (4) 由環(huán)的長度 = 鏈表總長度 - 起點(diǎn)到入口點(diǎn)的距離求出
a = (n - 1) * r + (L -a -x) (5)
從式子（5）以及上圖我們可以看出，從鏈表起點(diǎn)head開始到入口點(diǎn)的距離a,與從slow和fast的相遇點(diǎn)（如圖）到入口點(diǎn)的距離相等。
因此我們就可以分別用一個(gè)指針（ptr1, prt2），同時(shí)從head與slow和fast的相遇點(diǎn)出發(fā)，每一次操作走一步，直到ptr1 == ptr2，此時(shí)的位置也就是入口點(diǎn)！
到此第二個(gè)問題也已經(jīng)解決。

Node* findLoopStart(Node *head)
{
    Node *fast, *slow ;
    slow = fast = head ;
 
    while (slow != NULL && fast -> next != NULL)
    {
        slow = slow -> next ;
        fast = fast -> next -> next ;
        if (slow == fast) break ;
    }
    if (slow == NULL || fast -> next == NULL) return NULL ; //沒有環(huán)，返回NULL值
 
    Node * ptr1 = head ; //鏈表開始點(diǎn)
    Node * ptr2 = slow ; //相遇點(diǎn)
    while (ptr1 != ptr2) 
    {
        ptr1 = ptr1 -> next ;
        ptr2 = ptr2 -> next ;
    }
    return ptr1 ; //找到入口點(diǎn)

第3個(gè)問題，如果存在環(huán)，求環(huán)上節(jié)點(diǎn)的個(gè)數(shù)：

方式1：記錄下相遇節(jié)點(diǎn)存入臨時(shí)變量tempPtr，然后讓slow(或者fast，都一樣)繼續(xù)向前走slow = slow -> next；一直到slow == tempPtr; 此時(shí)經(jīng)過的步數(shù)就是環(huán)上節(jié)點(diǎn)的個(gè)數(shù)；
方式2： 從相遇點(diǎn)開始slow和fast繼續(xù)按照原來的方式向前走slow = slow -> next; fast = fast -> next -> next；直到二者再次項(xiàng)目，此時(shí)經(jīng)過的步數(shù)就是環(huán)上節(jié)點(diǎn)的個(gè)數(shù) 。
兩種方式本質(zhì)是一樣的都是在相遇點(diǎn)再次開始走一遍直到再次相遇。

問題4是如果存在環(huán)，求出鏈表的長度：
問題二已經(jīng)知道了起點(diǎn)到入口點(diǎn)的距離，問題三知道了環(huán)的長度r；
鏈表長度L = 起點(diǎn)到入口點(diǎn)的距離 + 環(huán)的長度r;

問題5是，求出環(huán)上距離任意一個(gè)節(jié)點(diǎn)最遠(yuǎn)的點(diǎn)（對面節(jié)點(diǎn)）

如下圖所示，點(diǎn)1和4、點(diǎn)2和5、點(diǎn)3和6分別互為”對面節(jié)點(diǎn)“ ，也就是換上最遠(yuǎn)的點(diǎn)，我們的要求是怎么求出換上任意一個(gè)點(diǎn)的最遠(yuǎn)點(diǎn)。

對于換上任意的一個(gè)點(diǎn)ptr0, 我們要找到它的”對面點(diǎn)“，可以這樣思考：同樣使用上面的快慢指針的方法，讓slow和fast都指向ptr0，每一步都執(zhí)行與上面相同的操作（slow每次跳一步，fast每次跳兩步），
當(dāng)fast = ptr0或者fast = prt0->next的時(shí)候slow所指向的節(jié)點(diǎn)就是ptr0的”對面節(jié)點(diǎn)“。

如上圖，我們想像一下，把環(huán)從ptro處展開，展開后可以是無限長的（如上在6后重復(fù)前面的內(nèi)容）如上圖。
現(xiàn)在問題就簡單了，由于slow移動(dòng)的距離永遠(yuǎn)是fast的一般，因此當(dāng)fast遍歷玩整個(gè)環(huán)長度r個(gè)節(jié)點(diǎn)的時(shí)候slow正好遍歷了r/2個(gè)節(jié)點(diǎn)，
也就是說，此時(shí)正好指向距離ptr0最遠(yuǎn)的點(diǎn)。

轉(zhuǎn)載原文：https://blog.csdn.net/doufei_...