快捷導(dǎo)航

C語(yǔ)言實(shí)例真題講解數(shù)據(jù)結(jié)構(gòu)中單向環(huán)形鏈表

更新時(shí)間：2022年04月11日 11:54:43 作者：三分苦

鏈表可以說(shuō)是一種最為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)了，而單向鏈表更是基礎(chǔ)中的基礎(chǔ)。鏈表是由一組元素以特定的順序組合或鏈接在一起的，不同元素之間在邏輯上相鄰，但是在物理上并不一定相鄰。在維護(hù)一組數(shù)據(jù)集合時(shí)，就可以使用鏈表，這一點(diǎn)和數(shù)組很相似

1、例題引入

鏈接直達(dá)：

環(huán)形鏈表

題目：

2、何為帶環(huán)鏈表

正常的單鏈表每個(gè)節(jié)點(diǎn)順次鏈接，最后一個(gè)節(jié)點(diǎn)指向NULL，如下：

而帶環(huán)鏈表的最后一個(gè)節(jié)點(diǎn)不再指向NULL了，指向的是前面任意一個(gè)節(jié)點(diǎn)，以此形成帶環(huán)鏈表，并一直循環(huán)下去。如下：

3、題解思路

我們可以將上述圖畫(huà)的抽象一點(diǎn)，在沒(méi)有進(jìn)入環(huán)之前我們用直線表示，進(jìn)入環(huán)之后用圈來(lái)表示，以此示意循環(huán)。此題需要用到我們之前講解的求中間節(jié)點(diǎn)和求倒數(shù)第k個(gè)節(jié)點(diǎn)的快慢指針的思想。定義兩個(gè)指針slow和fast均指向一開(kāi)始的位置。讓slow一次走一步，fast一次走兩步。

當(dāng)slow走到直線一半的位置時(shí)，此時(shí)的fast剛好就在環(huán)的入口點(diǎn)。

假設(shè)slow剛好走到環(huán)的入口點(diǎn)時(shí)，fast走到如下位置，此時(shí)fast開(kāi)始追趕模式

fast開(kāi)始追趕slow，假設(shè)fast在如下的位置開(kāi)始追上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;
}

單純從解體的角度看，此題并不復(fù)雜，僅需用到快慢指針的思想即可解決，單是由此題可以引出多個(gè)值得我們探討的問(wèn)題，以此來(lái)加深我們對(duì)環(huán)形鏈表的認(rèn)知，如下三大拓展問(wèn)題：

4、拓展問(wèn)題

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

答案：一定能。

證明：

當(dāng)slow走到中間的時(shí)候，fast一定進(jìn)環(huán)了，此時(shí)fast開(kāi)始追擊。我們假設(shè)slow進(jìn)環(huán)以后，slow和fast的距離是N，此時(shí)slow走1步，fast走2步，它們倆的距離縮短1變?yōu)镹-1。以此類推，每次追擊，距離縮小1，當(dāng)距離縮小為0時(shí)就追上了。綜上，一定能追上。

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

答案：不一定

證明：

我們先來(lái)討論slow一次走1步，fast一次走3步的情況。假設(shè)slow走了1步，fast走3步時(shí)剛好進(jìn)環(huán)，而當(dāng)slow剛好進(jìn)環(huán)的時(shí)候，fast可能已經(jīng)走了1圈，具體情況得看環(huán)的大小，此時(shí)slow和fast之間的距離為N。并假設(shè)環(huán)的長(zhǎng)度是C。

slow一次走1步，fast一次走3步，距離變?yōu)镹-2。由此可見(jiàn)，fast和slow每走一次，距離縮短2。此時(shí)就不難發(fā)現(xiàn)了，需要分類討論，當(dāng)N是偶數(shù)時(shí)，剛好可以追上，當(dāng)N是奇數(shù)時(shí)，追到最后距離為-1，此時(shí)就要再追了，意味著slow和fast之間的距離變成C-1。

繼續(xù)追擊，根據(jù)前面的分析，如果C-1是偶數(shù)，那么可以追上。如果C-1是奇數(shù)，那么就永遠(yuǎn)追不上了，將會(huì)無(wú)線循環(huán)追下去，可就是追不上。他們的差距N是由進(jìn)環(huán)前的長(zhǎng)度和環(huán)的長(zhǎng)度決定的，而這兩個(gè)又都是隨機(jī)的，所以N的值不確定，可奇可偶，又像剛剛那樣討論下去，出現(xiàn)奇數(shù)將一去不復(fù)返。

同理fast一次走4步也是這樣的討論，同樣都是不一定，不過(guò)這個(gè)時(shí)候是每走一次，距離縮短3。當(dāng)N是3的倍數(shù)就可以追上，當(dāng)不是3的倍數(shù)就要繼續(xù)討論了，有興趣的童鞋可以繼續(xù)鉆研下去，思想和fast一次走3步一樣，這里不過(guò)多贅述。

（3）鏈表環(huán)的入口點(diǎn)在哪呢？

當(dāng)我們搞清楚slow和fast分別走的距離時(shí)，入口點(diǎn)自然就明了了。

法一：

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

在具體講解之前，首先要搞清楚，不存在說(shuō)慢指針slow在里頭走了一圈，快指針fast還沒(méi)有追到slow，因?yàn)閒ast每次走2步，slow每次走1步，它倆間的距離每次都縮小1，所以只會(huì)越來(lái)越近，直到追到。最多最多也就快1圈，但從來(lái)也不會(huì)剛好滿1圈。所以下面很容易推出slow和fast分別走了多少。

假設(shè)：

【鏈表頭 - - - 入口點(diǎn)】：L

【入口點(diǎn) - - - 相遇點(diǎn)】：X

【環(huán)的長(zhǎng)度】：C

slow走的距離：L + X

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

解釋：

因?yàn)橄惹耙呀?jīng)提到slow不會(huì)都走了一圈還沒(méi)被追到，所以很容易推出slow的距離就是L+X

而快指針一次走2步，很可能會(huì)因?yàn)榄h(huán)過(guò)小導(dǎo)致在slow指針進(jìn)入入口點(diǎn)前，fast指針已經(jīng)走了好幾圈。簡(jiǎn)而言之3句話：

L很小，C很大，slow進(jìn)環(huán)前，fast可能在環(huán)里面，一圈都沒(méi)走完
L很大，C很小，slow進(jìn)環(huán)前，fast在里面走了很多圈了
但是slow進(jìn)環(huán)以后，在一圈之內(nèi)，fast一定追到slow，它們的距離最多C-1

根據(jù)一開(kāi)始說(shuō)的，fast走的距離是slow走的距離的2倍，可列出如下式子：

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

化簡(jiǎn)后：L+X = N*C 或 L = N*C - X 或 L = (N-1)*C + (C-X) 或 L + X = N*C

用此公式即可證明：一個(gè)指針從meet走，一個(gè)指針從head走，他們會(huì)在入口點(diǎn)相遇！

因?yàn)槭阶?N-1)*C表明從相遇點(diǎn)走了N-1圈后又回到了相遇點(diǎn)，此時(shí)再走C-X的距離就回到了入口點(diǎn)，由上得知，此公式確實(shí)讓它們回到了入口點(diǎn)。

用一道切實(shí)的題目來(lái)具體解出入口點(diǎn)的位置：

鏈接直達(dá)：

環(huán)形鏈表2.0-->尋找入口點(diǎn)

題目：

代碼如下：

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)
    {
        //判斷是否是帶環(huán)鏈表
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            struct ListNode* meet = slow;
            while (meet != head)
            {
                //求出相遇點(diǎn)
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    return NULL;
}

求相遇點(diǎn)還有另外一種方法：

找到相遇點(diǎn)meet后，讓meet做尾，讓下一個(gè)點(diǎn)做新鏈表的頭

此法顯的尤為巧妙，剛好轉(zhuǎn)換成了兩個(gè)鏈表求交點(diǎn)的問(wèn)題。因?yàn)榇藭r(shí)headA鏈表的尾部是meet，而headB鏈表的尾部也是meet，此時(shí)就意味著倆鏈表必會(huì)相交，而相交的地方就是入口點(diǎn)，兩鏈表相交正是博主上篇博文中所詳細(xì)講解的，這里就不過(guò)多強(qiáng)調(diào)了。

到此這篇關(guān)于C語(yǔ)言超詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)中單向環(huán)形鏈表的文章就介紹到這了,更多相關(guān)C語(yǔ)言單向環(huán)形鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: