什么是帶環(huán)鏈表：

帶環(huán)鏈表是鏈表最后一個(gè)結(jié)點(diǎn)的指針域不是指向空指針，而是指向鏈表之前的結(jié)點(diǎn)，這樣就形成了環(huán)狀的鏈表結(jié)構(gòu)。

如圖所示：

判斷鏈表是否帶環(huán)：

那么問題來了，如何判斷一個(gè)鏈表是否帶環(huán)呢？

這里我們?cè)俅芜\(yùn)用了快慢指針，但是快慢指針又該如何具體設(shè)置呢？

• 判斷思路：

先定義一個(gè)快指針fast，一個(gè)慢指針slow。

快指針一定是比慢指針先進(jìn)環(huán)的，當(dāng)slow進(jìn)環(huán)時(shí)，fast指針便開始了追slow指針，當(dāng)快指針和慢指針相遇的時(shí)候，快指針便追上了慢指針，此時(shí)就可以判斷該鏈表是有環(huán)的，但凡快指針指向空就說明該鏈表是不帶環(huán)的。

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

假設(shè)slow剛進(jìn)環(huán)時(shí)，fast與slow之間的距離為N，環(huán)的長(zhǎng)度為C。

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

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

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

…………………

圖為當(dāng)slow剛進(jìn)環(huán)時(shí)，假設(shè)fast所在的位置：

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

每次追擊，fast與slow之間的距離就縮小1，當(dāng)距離N縮小為0的時(shí)候，便追上了。

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

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

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

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

（1）當(dāng)N為偶數(shù)時(shí)，N每次縮小2，當(dāng)距離N縮小為0的時(shí)候，便追上了。

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

（2）當(dāng)N為奇數(shù)時(shí)，N每次縮小2，當(dāng)距離N縮小為1的時(shí)候，下次追擊二者距離扔縮小2，此時(shí)               fast就會(huì)超過slow，距離N變?yōu)?-1 ，也就是C - 1，這時(shí)又要對(duì)C  - 1進(jìn)行討論。

• 當(dāng)C - 1為偶數(shù)時(shí)就能追上。 
• 當(dāng)C - 1為奇數(shù)時(shí)就扔會(huì)錯(cuò)過，N再次變成C - 1，那么就會(huì)永遠(yuǎn)錯(cuò)過也就永遠(yuǎn)追不上。

所以這種情況不一定能追上，有可能永遠(yuǎn)追不上。 

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

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

（1）當(dāng)N為3的倍數(shù)時(shí)，N每次縮小3，當(dāng)距離N縮小為0的時(shí)候，便追上了。

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

（2）當(dāng)N不為3的倍數(shù)時(shí)，那么fast會(huì)與slow錯(cuò)過，至于錯(cuò)過時(shí)fast超過slow多少距離還需討論               （超過的距離取決于一開始N的長(zhǎng)度）。

• 當(dāng)追上后，fast超過slow距離為1時(shí)，此時(shí)fast追slow追擊距離為N即（C - 1），此時(shí)又要對(duì)C - 1進(jìn)行上述討論，即C - 1是否為3的倍數(shù)的討論。 
• 當(dāng)追上后，fast超過slow距離為2時(shí)，此時(shí)fast追slow追擊距離為N即（C - 2），此時(shí)又要對(duì)C - 2進(jìn)行上述討論，即C - 2是否為3的倍數(shù)的討論。

 所以這種情況只有當(dāng)N為3的倍數(shù)的時(shí)候才能追得上。

綜上：能不能追得上取決于兩個(gè)指針之間的距離N和環(huán)的大小C。

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

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

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

總結(jié)：

設(shè)置fast一次走2步，slow一次走1步的時(shí)候最保險(xiǎn)。 因?yàn)榭炻羔樝嗑郚，每追擊一次N就減1，總會(huì)減到0，N縮小到0就是追到了。

環(huán)形鏈表 I

環(huán)形鏈表

OJ鏈接

給你一個(gè)鏈表的頭節(jié)點(diǎn) head ，判斷鏈表中是否有環(huán)。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos 不作為參數(shù)進(jìn)行傳遞 。僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。

如果鏈表中存在環(huán) ，則返回 true 。 否則，返回 false 。

示例 1：

輸入：

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

輸出：

true

解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。

示例 2：

輸入：

head = [1,2], pos = 0

輸出：

true

解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。

示例 3：

輸入：

head = [1], pos = -1

輸出：

false

解釋：鏈表中沒有環(huán)。

/**
 * 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;
}

思路：

運(yùn)用上述判斷環(huán)形鏈表的結(jié)論，fast一次走2步，slow每次走1步，只要是環(huán)狀就一定會(huì)追的到。

找?guī)Лh(huán)形鏈表入環(huán)的第一個(gè)結(jié)點(diǎn)：

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

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

當(dāng)快指針追到慢指針時(shí)，假設(shè)相遇點(diǎn)為meet，slow指針和fast指針在如圖所示的：

注意：

這里快指針一定是先進(jìn)環(huán)，slow后進(jìn)環(huán)。

slow指針進(jìn)環(huán)后，在走一圈的時(shí)間內(nèi)，一定是會(huì)被fast追上的 。

 思路：

在是slow指針和fast指針，同時(shí)從head頭開始走，直到在meet點(diǎn)相遇，又因?yàn)閒ast指針的速度為slow指針?biāo)俣鹊亩?，那么就一定滿足一個(gè)等式關(guān)系：

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

還需討論的是當(dāng)slow進(jìn)環(huán)時(shí)，fast在環(huán)內(nèi)走了多久的問題：

• 當(dāng)L足夠長(zhǎng)而C很小時(shí)：slow進(jìn)環(huán)時(shí)fast可能已經(jīng)在環(huán)內(nèi)走了好多圈了（假設(shè)為n圈）。
• 當(dāng)L很小而C足夠大時(shí)：slow進(jìn)環(huán)時(shí)fast可能在環(huán)內(nèi) 連一圈還沒走。

綜合考慮之后再結(jié)合上述等式關(guān)系變得到下列等式：

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

化簡(jiǎn)得：

L = n * C - X

 這個(gè)公式充分說明了，一個(gè)指針從head走，一個(gè)指針從相遇點(diǎn)meet走，并且每次都走一步，一     直走下去，它們最終會(huì)在環(huán)的入口點(diǎn)相遇?。。?/p>

環(huán)形鏈表 II

環(huán)形鏈表 II

OJ鏈接

給定一個(gè)鏈表的頭節(jié)點(diǎn)  head ，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無環(huán)，則返回 null。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。不允許修改 鏈表。

示例 1：

輸入：

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

輸出：

返回索引為 1 的鏈表節(jié)點(diǎn)

解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。 示例 2：

輸入：

head = [1,2], pos = 0

輸出：

返回索引為 0 的鏈表節(jié)點(diǎn)

解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。

示例 3：

輸入：

head = [1], pos = -1

輸出：

返回 null

解釋：鏈表中沒有環(huán)。

/**
 * 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： 

先運(yùn)用上述判斷環(huán)形鏈表的結(jié)論找到相遇點(diǎn)，再運(yùn)用上述找環(huán)形入口點(diǎn)的結(jié)論，就能輕松找到環(huán)的入口點(diǎn)。

思路2：

先運(yùn)用上述判斷環(huán)形鏈表的結(jié)論找到相遇點(diǎn)，再將相遇點(diǎn)斷開，這時(shí)就變成了上一篇博客找相交鏈表公共結(jié)點(diǎn)的問題，示意圖如下：

 參考代碼如下：

/**
 * 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;
}

到此這篇關(guān)于C語(yǔ)言 推理證明帶環(huán)鏈表詳細(xì)過程的文章就介紹到這了,更多相關(guān)C語(yǔ)言 帶環(huán)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論