引言

??
上一篇 【神秘海域】數(shù)據(jù)結(jié)構(gòu)與算法 內(nèi)容是 單鏈表及其接口

而本篇內(nèi)容是對單鏈表的一個 非常重要 的補充： 帶環(huán)單鏈表 。它，是大廠面試時可能會提問的內(nèi)容，非常的重要！

本篇就是要結(jié)合題目來 詳細分析一下 單鏈表的帶環(huán)問題

帶環(huán)單鏈表之前 : 快慢指針

??
在詳細分析 帶環(huán)單鏈表 之前，先分析兩道題來了解一個非常重要的算法思路：快慢指針

題1：單鏈表的中間結(jié)點

??
原題描述是這樣的:

給定一個頭結(jié)點為 head 的非空單鏈表，返回鏈表的中間結(jié)點。

如果有兩個中間結(jié)點，則返回第二個中間結(jié)點。

示例 1：

輸入：[1,2,3,4,5]
輸出：此列表中的結(jié)點 3 (序列化形式：[3,4,5])
返回的結(jié)點值為 3 (測評系統(tǒng)對該結(jié)點序列化表述是 [3,4,5])
注意，我們返回了一個 ListNode 類型的對象 ans ，這樣：
ans.val = 3 , ans.next.val = 4 , ans.next.next.val = 5 , 以及 ans.next.next.next = NULL .

示例 2：

輸入：[1,2,3,4,5,6]
輸出：此列表中的結(jié)點 4 (序列化形式：[4,5,6])
由于該列表 有兩個中間結(jié)點 ，值分別為 3 和 4，我們 返回第二個結(jié)點

原題鏈接： Leetcode - 876. 鏈表的中間結(jié)點

這一題的解法，就需要使用到 快慢指針 的思路

那么什么是 快慢指針 ？即，使用兩個 移動速度不同 的指針在 數(shù)組 或 鏈表 等 序列結(jié)構(gòu)上移動。

本題思路：

求鏈表的中間節(jié)點，就可以定義兩個指針 : pslow 慢指針 、 pfast 快指針

在本題中，快指針每次 移動兩個節(jié)點 ，慢指針每次 移動一個節(jié)點 ，當快指針 走過尾節(jié)點為空(鏈表節(jié)點為單數(shù)) 或 指向尾節(jié)點(鏈表節(jié)點為雙數(shù)) 時，慢指針應該 正好在中間節(jié)點

此時 慢指針所指節(jié)點 即為題目所求

代碼實現(xiàn)：

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* pfast = head;
    struct ListNode* pslow = head;
    while(pfast && pfast->next)
    {
        pfast = pfast->next->next;
        pslow = pslow->next;
    }

    return pslow;
}

題2：鏈表中倒數(shù)最后k個結(jié)點

??
此題描述是這樣的：

例如，輸入 {1,2,3,4,5}, 2 時，對應的鏈表結(jié)構(gòu)如下圖所示：

其中藍色部分為該鏈表的最后2個結(jié)點，所以 返回倒數(shù)第2個結(jié)點（也即結(jié)點值為4的結(jié)點） 即可，系統(tǒng)會打印后面所有的節(jié)點來比較。

示例 1：

輸入：{1,2,3,4,5},2

返回值：{4,5}

說明：返回倒數(shù)第2個節(jié)點4，系統(tǒng)會打印后面所有的節(jié)點來比較。

示例 2:

輸入：{2},8

返回值：{}

原題鏈接：Nowcoder - JZ22 鏈表中倒數(shù)最后k個結(jié)點

本題的思路也是使用快慢指針，但是與上一題不同的是，本題是先走為快指針 與 后走為慢指針

本題思路：

定義兩個指針 : pslow 慢指針 、 pfast 快指針，兩指針均 一步一步走

快指針 先走 k 步，但同時要保證 快指針沒走到空 ，如果 k 步?jīng)]走完就已經(jīng)走到空了，就表示鏈表沒那么長

然后 慢指針 與 快指針 同時開始走，直到快指針走到空

此時 慢指針所指節(jié)點 即為題目所求

代碼實現(xiàn)：

struct ListNode* FindKthToTail(struct ListNode* pHead, int k )
{
    struct ListNode* pfast = pHead;
    struct ListNode* pslow = pHead;
    
    while(k--)
    {
        if(pfast)
        {
            pfast = pfast->next;
        }
        else
        {// 快指針指向空，即鏈表長度不到 k，直接返回 NULL
            return NULL;
        }
    }
    while(pfast)
    {
        pfast = pfast->next;
        pslow = pslow->next;
    }

    return pslow;
}

在分析帶環(huán)鏈表之前，需要 需要了解一下 快慢指針 ，因為 帶環(huán)鏈表的分析 是根據(jù) 快慢指針 分析的.

帶環(huán)鏈表分析

??
分析 帶環(huán)鏈表 ，先 由一道題來引入：

題：環(huán)形鏈表

??
此題描述：

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

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

如果鏈表中存在環(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)

原題鏈接：Leetcode - 141. 環(huán)形鏈表

本題的思路也非常簡單：

如果鏈表帶環(huán)，那么使用 快慢指針：pfast一次走兩步，pslow一次走一步

兩個指針就一定能相遇，因為 兩指針均入環(huán)之后，兩指針的距離是在一步步靠近的

不能相遇，就代表 鏈表不帶環(huán)

代碼實現(xiàn)：

bool hasCycle(struct ListNode *head)
{
    if(head == NULL)
        return false;

    struct ListNode* pfast = head;
    struct ListNode* pslow = head;

    while(pfast && pfast->next)
    {
        pfast = pfast->next->next;
        pslow = pslow->next;

        if(pfast == pslow)
            return true;
    }

    return false;
}

OK，帶環(huán)鏈表的題做出來了

但是并沒有結(jié)束 如果只是這樣 怎么會有大廠提問呢？

帶環(huán)鏈表的問題

??
在 鏈表帶環(huán) 的基礎上，還會延伸出幾個問題：

1. 快指針一次走兩步，慢指針一次走一步，兩指針一定會相遇嗎？為什么？
2. 如果 快指針一次走兩步呢？三步呢？四步呢？為什么？
3. 怎么找到帶環(huán)鏈表的 入環(huán)節(jié)點 ？

這才是 帶環(huán)鏈表 真正需要知道的東西~

?帶環(huán)鏈表深入分析? *

??

問題1

??
快指針一次走兩步，慢指針一次走一步，兩指針一定會相遇嗎？為什么？

來詳細分析一下：

畫圖抽象圖來分析，一個帶環(huán)鏈表，抽象的形式可以看作：

快慢指針 同時 從首節(jié)點開始走，快指針走得快，慢指針走得慢

所以慢指針入環(huán)時，快指針早就已經(jīng)入環(huán)了

此時的情況可能是(設一下，只是假設)：

兩個指針都入環(huán)之后，快指針開始在環(huán)內(nèi)追逐慢指針：

因為 當這樣的兩個指針都入環(huán)之后，兩個指針之間的距離變化就變?yōu)榱?每走一步減一

所以，必定會相遇

問題2

??
如果 快指針一次走三步呢？四步呢？為什么？

快指針一次走多步，就需要看情況來分析了

快指針一次走三步：

上邊我們分析了 快指針一次走兩步 時的相遇情況：當兩個指針都入環(huán)之后，其之間的距離是以 每次縮小 1 變化的

那么如果 快指針一次走三步，那么 兩個指針都入環(huán)之后，其之間的距離就是 以 每次縮小 2 變化的

每次縮小 2，會造成什么情況呢？

設 慢指針入環(huán)時，快指針和慢指針之間的距離為 X，環(huán)的長度為 C，那么就會有兩種情況：當 X 為奇數(shù)，當 X 為偶數(shù)

情況 1： X 為 偶數(shù)

當 X(兩指針之間的距離) 為偶數(shù)，兩指針距離又是 每次減2 的變化，所以一定能相遇

情況 2： X 為 奇數(shù)此情況，快指針 超過 慢指針，但是由于快指針的移動是不連續(xù)的，所以兩指針并不會相遇

其之間的距離變成了 -1，但是現(xiàn)在并不能直接判斷是否能相遇，因為不能保證后面的追擊能不能相遇

又因為 我們設環(huán)的長度為 C，所以此時 兩指針之間的距離也是 C-1

所以，就又分為了兩種情況：當 C-1 為奇數(shù)，當 C-1 為偶數(shù)

當 C-1 為 偶數(shù)的時候，這時，下次追擊就可以相遇

當 C-1 為 奇數(shù)的時候，這時，就永遠不會相遇了

為什么永遠不會相遇？

當 C-1 為奇數(shù)時，也就意味著本次追擊的 X(兩指針之間的距離) 為奇數(shù)

X 為奇數(shù)，就又會出現(xiàn) 兩指針之間的距離等于 -1 的情況，距離就有變成了 C-1

所以，當 C-1 為奇數(shù)時，永遠不會遇到

快指針一次走四步：

當快指針 一次走四步 的時候，按照 一次走三步 的思路進行分析

1. X 為 3 的倍數(shù)，可以相遇
2. X 不為 3 的倍數(shù)，且 C-1 或 C-2 也不為 3 的倍數(shù)，就永遠無法相遇
3. C-1 和 C-2 ，需要更詳細的分析

也就是說，快指針 一次走多步 能不能與慢指針相遇是 不確定的。

實際的情況，與 環(huán)的長度 和 入環(huán)前鏈表的長度 都有關(guān)系，需要 具體情況具體分析

問題3

??
怎么找到帶環(huán)鏈表的 入環(huán)節(jié)點 ？

能夠找到入環(huán)節(jié)點的一個前提是：快指針已經(jīng)與慢指針相遇。

詳細分析一下：

首先還是畫圖假設一下：

先思考一個問題：慢指針 從入環(huán)到被追上 ，走過的長度 是不是如假設的那樣，會不會已經(jīng)走了一圈后才被追上的？

答案是：不會 。

即使環(huán)再小，只有一個節(jié)點，慢指針那么在入環(huán)的一刻，就已經(jīng)與快指針相遇了

如果環(huán)再長，慢指針也不可能走過一圈，因為快指針的速度是慢指針的兩倍，慢指針如果走 超過一圈 ，那么快指針只會走 超過兩圈

所以，慢指針一定是 在一圈之內(nèi)被追上的，所以假設 是成立的。

參考圖來看，慢指針 從開始 到 與快指針相遇，走過的距離就是 ：L + X

那么 快指針 走過的距離就是 ： 2 * (L + X)

快指針走過的距離還可以怎么表示呢？

快指針走過的距離 還可以這樣表示：L + X + N * C (N表示走過的圈數(shù))

因為 快指針先入環(huán)，所以在慢指針入環(huán)之前，快指針很可能在環(huán)內(nèi)已經(jīng)走過幾圈了

1. 當 L 很大 C很小時，快指針可能已經(jīng)走了 N 圈了
2. 當 L 很小 C 很大時，快指針可能沒有走超過一圈

所以，快指針 從開始 到 與慢指針相遇 走過的距離，就可以寫成一個等式：

2 * (L + X) = L + X + N*C

化簡一下就是： L + X = N * C

這個式子有什么用呢？

其實，這個等式說明：

如果，有兩個指針同時以一次一步的速度，一個從 鏈表的首節(jié)點 開始，另一個從 快慢指針相遇點 開始，兩個指針會在環(huán)的入口節(jié)點相遇。

為什么呢？

L + X = N * C 可以寫為 --> L = N * C - X

一個指針從 鏈表首屆點開始走，走過 L 長度 它的位置在入環(huán)節(jié)點

一個指針從 快慢指針相遇點 開始走， 走過 N * C 的長度，它的位置還在 快慢指針相遇點 ，但是如果走過 N * C - X 的長度，那么它的位置就也在 入環(huán)節(jié)點了，因為 入環(huán)節(jié)點到快慢指針相遇點的距離是 X

此時，入環(huán)節(jié)點就找到了。

題：尋找入環(huán)節(jié)點

??
分析完如何尋找入環(huán)節(jié)點，下面來嘗試把這道題給做了：

題目描述：

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

如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達，則鏈表中存在環(huán)。

為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置**（索引從 0 開始）**。如果 pos 是 -1，則在該鏈表中沒有環(huán)。

注意：pos 不作為參數(shù)進行傳遞，僅僅是為了標識鏈表的實際情況

不允許修改 鏈表

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

原題鏈接：Leetcode - 142. 環(huán)形鏈表 II

代碼實現(xiàn)：

// 大體思路與判斷有環(huán)差不多
// 但是 有環(huán)時不能直接返回
struct ListNode *detectCycle(struct ListNode *head)
{
    if(head == NULL)
        return NULL;

    struct ListNode* pfast = head;
    struct ListNode* pslow = head;

    while(pfast && pfast->next)
    {
        pfast = pfast->next->next;
        pslow = pslow->next;

        if(pfast == pslow)		// 有環(huán)
        {
            struct ListNode* phead = head;
            while(phead != pslow)		//使 兩個指針 分別從 首節(jié)點和相遇點 一次一步 移動，直到相遇
            {
                phead = phead->next;
                pslow = pslow->next;
            }
            return phead;
        }
    }

    return NULL;
}

結(jié)語

??
本篇是對 單鏈表帶環(huán)問題 的一個深入探索，單鏈表帶環(huán)問題是 單鏈表中一個非常重要的應用 和 對單鏈表非常重要的理解。同時，他已經(jīng)進入了大廠面試可能會考的范疇，重要的是對 單鏈表帶環(huán)問題的深入分析 ，而不是簡單的判斷是否有環(huán)。

本篇文章到此結(jié)束

感謝閱讀~

求評論、點贊、收藏~

博主其他文章推薦：
??【神秘海域】[動圖] 掌握 單鏈表 只需要這篇文章~ 「超詳細」
??【程序員的自我修養(yǎng)】[動態(tài)圖文] 理解編譯到鏈接的過程 [編譯與鏈接一]
??【程序員的自我修養(yǎng)】[動態(tài)圖文] 超詳解函數(shù)棧幀

有興趣的可以關(guān)注一下博主的專欄：
?專欄：神秘海域：數(shù)據(jù)結(jié)構(gòu)與算法
?專欄：《程序員的自我修養(yǎng)》文章來源地址http://www.zghlxwxcb.cn/news/detail-402624.html

到了這里，關(guān)于【神秘海域】[動圖] 結(jié)合題目-手把手帶你剖析 “帶環(huán)鏈表”的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！