什么是帶環鏈表：

帶環鏈表是鏈表最后一個結點的指針域不是指向空指針，而是指向鏈表之前的結點，這樣就形成了環狀的鏈表結構。

如圖所示：

判斷鏈表是否帶環：

那么問題來了，如何判斷一個鏈表是否帶環呢？

這里我們再次運用了快慢指針，但是快慢指針又該如何具體設置呢？

• 判斷思路：

先定義一個快指針fast，一個慢指針slow。

快指針一定是比慢指針先進環的，當slow進環時，fast指針便開始了追slow指針，當快指針和慢指針相遇的時候，快指針便追上了慢指針，此時就可以判斷該鏈表是有環的，但凡快指針指向空就說明該鏈表是不帶環的。

• 那么快慢指針一次各走幾步最合適呢？

假設slow剛進環時，fast與slow之間的距離為N，環的長度為C。

• 這里我們要多組討論一下：（先討論有代表的兩組）

1.slow一次走1步，fast一次走2步一定能追上嗎？

2.slow一次走1步，fast一次走3步一定能追上嗎？

…………………

圖為當slow剛進環時，假設fast所在的位置：

1.slow一次走1步，fast一次走2步一定能追上嗎？

每次追擊，fast與slow之間的距離就縮小1，當距離N縮小為0的時候，便追上了。

N - 1，N - 2，N - 3，……，0

所以這種情況一定能追上。

2.slow一次走1步，fast一次走3步一定能追上嗎？

每次追擊，fast與slow之間的距離就縮小2，這里要對N進行討論：

（1）當N為偶數時，N每次縮小2，當距離N縮小為0的時候，便追上了。

? ? ? ? ?N - 2，N - 4，N - 6，……，0

（2）當N為奇數時，N每次縮小2，當距離N縮小為1的時候，下次追擊二者距離扔縮小2，此時? ? ? ? ? ? ? ?fast就會超過slow，距離N變為 -1 ，也就是C - 1，這時又要對C? - 1進行討論。

• 當C - 1為偶數時就能追上。?
• 當C - 1為奇數時就扔會錯過，N再次變成C - 1，那么就會永遠錯過也就永遠追不上。

所以這種情況不一定能追上，有可能永遠追不上。?

3.slow一次走1步，fast一次走4步一定能追上嗎？?

每次追擊，fast與slow之間的距離就縮小3，這里又要對N進行討論：

（1）當N為3的倍數時，N每次縮小3，當距離N縮小為0的時候，便追上了。

? ? ? ? ?N - 3，N - 6，N - 9，……，0

（2）當N不為3的倍數時，那么fast會與slow錯過，至于錯過時fast超過slow多少距離還需討論? ? ? ? ? ? ? ?（超過的距離取決于一開始N的長度）。

• 當追上后，fast超過slow距離為1時，此時fast追slow追擊距離為N即（C - 1），此時又要對C - 1進行上述討論，即C - 1是否為3的倍數的討論。?
• 當追上后，fast超過slow距離為2時，此時fast追slow追擊距離為N即（C - 2），此時又要對C - 2進行上述討論，即C - 2是否為3的倍數的討論。

?所以這種情況只有當N為3的倍數的時候才能追得上。

綜上：能不能追得上取決于兩個指針之間的距離N和環的大小C。

下面提供一個結論個人小結：（僅供參考，可能存在局限性）

只要快慢指針的速度差是2的時候，就可能會出現永遠追不上的問題。假設fast與slow的速度差為x，那么fast追趕slow一次，他們之間的距離就減少x，途中有可能剛好追上，也有可能錯過。當錯過的時候，fast在slow前面，這時fast超過slow的距離的取值只可能是在[1?~?(x?-?1)]之間（x取整數）。同時任意一個正整數，假設記作m，（m > x）當m整除一個整數x有余數時，對這個整數m減去[1?~?(x?-?1)]中任意一個值，總能找到一個值x，使得m - x的值能夠整除x。所以無論環的長度為多長，假設環的長度為C，總有C減去[1?~?(x?-?1)]中任意一個值，使得C?-?x能夠整除x并且沒余數，既然沒余數那就是剛好追上的情況。

當fast和slow的速度差為2時，即x = 2的時候，C?-?x，x屬于[1?~?(x?-?1)]，那么C?-?x就只能是C?-?1，那么當C?-?1去整除2的時候，如果C?-?1為奇數，那么C?-?1整除2必然有余數，并且余數為1，下次還是C?-?1去整除2，還是會余1，所以這時fast就永遠追不上slow。

總結：

設置fast一次走2步，slow一次走1步的時候最保險。 因為快慢指針相距N，每追擊一次N就減1，總會減到0，N縮小到0就是追到了。

環形鏈表 I

環形鏈表

OJ鏈接

給你一個鏈表的頭節點 head ，判斷鏈表中是否有環。

如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos 不作為參數進行傳遞?。僅僅是為了標識鏈表的實際情況。

如果鏈表中存在環?，則返回 true 。 否則，返回 false 。

示例 1：

輸入：

head = [3,2,0,-4], pos = 1

輸出：

true

解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例?2：

輸入：

head = [1,2], pos = 0

輸出：

true

解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：

head = [1], pos = -1

輸出：

false

解釋：鏈表中沒有環。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head)
{
    struct ListNode* fast, *slow;
    fast = slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast)
        return true;
    }
 
    return false;
}

思路：

運用上述判斷環形鏈表的結論，fast一次走2步，slow每次走1步，只要是環狀就一定會追的到。

找帶環形鏈表入環的第一個結點：

接下來更深層次的問題來了，帶環鏈表環的入口該怎么找呢？

以后帶環問題通常都用fast一次走2步，slow一次走1步。

當快指針追到慢指針時，假設相遇點為meet，slow指針和fast指針在如圖所示的：

注意：

這里快指針一定是先進環，slow后進環。

slow指針進環后，在走一圈的時間內，一定是會被fast追上的?。

?思路：

在是slow指針和fast指針，同時從head頭開始走，直到在meet點相遇，又因為fast指針的速度為slow指針速度的二倍，那么就一定滿足一個等式關系：

快指針走的距離?= 慢指針走的距離 * 2

還需討論的是當slow進環時，fast在環內走了多久的問題：

• 當L足夠長而C很小時：slow進環時fast可能已經在環內走了好多圈了（假設為n圈）。
• 當L很小而C足夠大時：slow進環時fast可能在環內?連一圈還沒走。

綜合考慮之后再結合上述等式關系變得到下列等式：

L + nC + X = 2 * (L+ X)?

化簡得：

L = n * C - X

?這個公式充分說明了，一個指針從head走，一個指針從相遇點meet走，并且每次都走一步，一? ? ?直走下去，它們最終會在環的入口點相遇！！！

環形鏈表 II

環形鏈表 II

OJ鏈接

給定一個鏈表的頭節點 ?head?，返回鏈表開始入環的第一個節點。?如果鏈表無環，則返回?null。

如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。不允許修改 鏈表。

示例 1：

輸入：

head = [3,2,0,-4], pos = 1

輸出：

返回索引為 1 的鏈表節點

解釋：鏈表中有一個環，其尾部連接到第二個節點。 示例?2：

輸入：

head = [1,2], pos = 0

輸出：

返回索引為 0 的鏈表節點

解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：

head = [1], pos = -1

輸出：

返回 null

解釋：鏈表中沒有環。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head)
{
    struct ListNode* fast, *slow;
    slow = fast = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast)
        {
            struct ListNode* meet = slow;
            while(head != meet)
            {
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    return NULL;
}

思路1：?

先運用上述判斷環形鏈表的結論找到相遇點，再運用上述找環形入口點的結論，就能輕松找到環的入口點。

思路2：

先運用上述判斷環形鏈表的結論找到相遇點，再將相遇點斷開，這時就變成了上一篇博客找相交鏈表公共結點的問題，示意圖如下：

?參考代碼如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head)
{
    struct ListNode* fast, *slow;
    slow = fast = head;
    int len1 = 0,len2 = 0;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast)
        {
            struct ListNode* shortList, *longList, *meet, *longTail, *shortTail;
            longList = longTail = head;
            meet = shortList = shortTail = slow->next;
            slow->next = NULL;
            while(shortTail)
            {
                shortTail = shortTail->next;
                len1++;
            }
            while(longTail)
            {
                longTail = longTail->next;
                len2++;
            }
            int gap = abs(len1 - len2);
            if(len1 > len2)
            {
                longList = meet;
                shortList = head;
            }       
            while(gap--)
            {
                longList = longList->next;
            }     
            while(shortList != longList)
            {
                longList = longList->next;
                shortList = shortList->next;
            }
            return longList;
        }
    }
    return NULL;
}