C語言範例真題講解資料結構中單向環形連結串列

目錄

1、例題引入

連結直達：

環形連結串列

題目：

2、何為帶環連結串列

 正常的單連結串列每個節點順次連結，最後一個節點指向NULL，如下：

 而帶環連結串列的最後一個節點不再指向NULL了，指向的是前面任意一個節點，以此形成帶環連結串列，並一直迴圈下去。如下：

3、題解思路

我們可以將上述圖畫的抽象一點，在沒有進入環之前我們用直線表示，進入環之後用圈來表示，以此示意迴圈。此題需要用到我們之前講解的求中間節點和求倒數第k個節點的快慢指標的思想。定義兩個指標slow和fast均指向一開始的位置。 讓slow一次走一步，fast一次走兩步。

當slow走到直線一半的位置時，此時的fast剛好就在環的入口點。

假設slow剛好走到環的入口點時，fast走到如下位置，此時fast開始追趕模式

 fast開始追趕slow，假設fast在如下的位置開始追上slow

程式碼如下：

bool hasCycle(struct ListNode *head) {
    struct ListNode*slow=head;
    struct ListNode*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}

單純從解體的角度看，此題並不複雜，僅需用到快慢指標的思想即可解決，單是由此題可以引出多個值得我們探討的問題，以此來加深我們對環形連結串列的認知，如下三大拓展問題：

4、拓展問題

• （1）slow一次走1步，fast一次走2步，一定能追上嗎？

 答案：一定能。

證明：

當slow走到中間的時候，fast一定進環了，此時fast開始追擊。我們假設slow進環以後，slow和fast的距離是N，此時slow走1步，fast走2步，它們倆的距離縮短1變為N-1。以此類推，每次追擊，距離縮小1，當距離縮小為0時就追上了。綜上，一定能追上。

• （2）slow一次走1步，fast一次走3步，能追上嗎？fast一次走4步呢？n步呢？  

答案：不一定

證明：

我們先來討論slow一次走1步，fast一次走3步的情況。假設slow走了1步，fast走3步時剛好進環，而當slow剛好進環的時候，fast可能已經走了1圈，具體情況得看環的大小，此時slow和fast之間的距離為N。並假設環的長度是C。

slow一次走1步，fast一次走3步，距離變為N-2。由此可見，fast和slow每走一次，距離縮短2。此時就不難發現了，需要分類討論，當N是偶數時，剛好可以追上，當N是奇數時，追到最後距離為-1，此時就要再追了，意味著slow和fast之間的距離變成C-1。

繼續追擊，根據前面的分析，如果C-1是偶數，那麼可以追上。如果C-1是奇數，那麼就永遠追不上了，將會無線迴圈追下去，可就是追不上。他們的差距N是由進環前的長度和環的長度決定的，而這兩個又都是隨機的，所以N的值不確定，可奇可偶，又像剛剛那樣討論下去，出現奇數將一去不復返。

同理fast一次走4步也是這樣的討論，同樣都是不一定，不過這個時候是每走一次，距離縮短3。當N是3的倍數就可以追上，當不是3的倍數就要繼續討論了，有興趣的童鞋可以繼續鑽研下去，思想和fast一次走3步一樣，這裡不過多贅述。

• （3）連結串列環的入口點在哪呢？

 當我們搞清楚slow和fast分別走的距離時，入口點自然就明瞭了。

法一：

slow一次走1步，fast一次走2步，那麼fast走的距離是slow的2倍

在具體講解之前，首先要搞清楚，不存在說慢指標slow在裡頭走了一圈，快指標fast還沒有追到slow，因為fast每次走2步，slow每次走1步，它倆間的距離每次都縮小1，所以只會越來越近，直到追到。最多最多也就快1圈，但從來也不會剛好滿1圈。所以下面很容易推出slow和fast分別走了多少。

假設：

【連結串列頭 - - - 入口點】：L

【入口點 - - - 相遇點】：X

【環的長度】：C

slow走的距離：L + X

fast走的距離：L + N*C + X

解釋：

因為先前已經提到slow不會都走了一圈還沒被追到，所以很容易推出slow的距離就是L+X

而快指標一次走2步，很可能會因為環過小導致在slow指標進入入口點前，fast指標已經走了好幾圈。簡而言之3句話：

• L很小，C很大，slow進環前，fast可能在環裡面，一圈都沒走完
• L很大，C很小，slow進環前，fast在裡面走了很多圈了
• 但是slow進環以後，在一圈之內，fast一定追到slow，它們的距離最多C-1

根據一開始說的，fast走的距離是slow走的距離的2倍，可列出如下式子：

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

化簡後：L+X = N*C     或    L = N*C - X     或     L = (N-1)*C + (C-X)     或     L + X = N*C

用此公式即可證明：一個指標從meet走，一個指標從head走，他們會在入口點相遇！

因為式子(N-1)*C表明從相遇點走了N-1圈後又回到了相遇點，此時再走C-X的距離就回到了入口點，由上得知，此公式確實讓它們回到了入口點。

用一道切實的題目來具體解出入口點的位置：

連結直達：

環形連結串列2.0-->尋找入口點

題目：

 程式碼如下：

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)
    {
        //判斷是否是帶環連結串列
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            struct ListNode* meet = slow;
            while (meet != head)
            {
                //求出相遇點
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    return NULL;
}

求相遇點還有另外一種方法：

找到相遇點meet後，讓meet做尾，讓下一個點做新連結串列的頭

此法顯的尤為巧妙，剛好轉換成了兩個連結串列求交點的問題。因為此時headA連結串列的尾部是meet，而headB連結串列的尾部也是meet，此時就意味著倆連結串列必會相交，而相交的地方就是入口點，兩連結串列相交正是博主上篇博文中所詳細講解的，這裡就不過多強調了。

到此這篇關於C語言超詳細講解資料結構中單向環形連結串列的文章就介紹到這了,更多相關C語言 單向環形連結串列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！