腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

C語言?推理證明帶環(huán)鏈表詳細(xì)過程

更新時間：2022年04月09日 09:25:57 作者：yy_上上謙

單鏈表中同樣也有具有挑戰(zhàn)性的題目，鏈表的帶環(huán)問題可以說是眾多難題中的佼佼者，在這里可能更看重的是邏輯推理和證明的過程

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

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

如圖所示：

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

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

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

判斷思路：

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

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

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

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

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

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

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

…………………

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

總結(jié)：

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

環(huán)形鏈表 I

環(huán)形鏈表

OJ鏈接

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

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

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

示例 1：

輸入：

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

輸出：

true

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

示例 2：

輸入：

head = [1,2], pos = 0

輸出：

true

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

示例 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;
}

思路：

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

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

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

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

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

注意：

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

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

思路：

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

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

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

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

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

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

化簡得：

L = n * C - X

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

環(huán)形鏈表 II

OJ鏈接

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

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

示例 1：

輸入：

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

輸出：

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

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

輸入：

head = [1,2], pos = 0

輸出：

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

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

示例 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：

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

思路2：

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

參考代碼如下：

/**
 * 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語言推理證明帶環(huán)鏈表詳細(xì)過程的文章就介紹到這了,更多相關(guān)C語言帶環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: