欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2022年04月11日 11:54:43   作者:三分苦  
鏈表可以說是一種最為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)了,而單向鏈表更是基礎(chǔ)中的基礎(chǔ)。鏈表是由一組元素以特定的順序組合或鏈接在一起的,不同元素之間在邏輯上相鄰,但是在物理上并不一定相鄰。在維護一組數(shù)據(jù)集合時,就可以使用鏈表,這一點和數(shù)組很相似

目錄

1、例題引入

鏈接直達:

環(huán)形鏈表

題目:

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

 正常的單鏈表每個節(jié)點順次鏈接,最后一個節(jié)點指向NULL,如下:

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

3、題解思路

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

當slow走到直線一半的位置時,此時的fast剛好就在環(huán)的入口點。

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

 fast開始追趕slow,假設(shè)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;
}

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

4、拓展問題

  • (1)slow一次走1步,fast一次走2步,一定能追上嗎?

 答案:一定能。

證明:

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

  • (2)slow一次走1步,fast一次走3步,能追上嗎?fast一次走4步呢?n步呢?  

答案:不一定

證明:

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

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

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

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

  • (3)鏈表環(huán)的入口點在哪呢?

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

法一:

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

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

假設(shè):

【鏈表頭 - - - 入口點】:L

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

【環(huán)的長度】:C

slow走的距離:L + X

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

解釋:

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

而快指針一次走2步,很可能會因為環(huán)過小導(dǎo)致在slow指針進入入口點前,fast指針已經(jīng)走了好幾圈。簡而言之3句話:

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

根據(jù)一開始說的,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的距離就回到了入口點,由上得知,此公式確實讓它們回到了入口點。

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

鏈接直達:

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

題目:

 代碼如下:

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)
            {
                //求出相遇點
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    return NULL;
}

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

找到相遇點meet后,讓meet做尾,讓下一個點做新鏈表的頭

此法顯的尤為巧妙,剛好轉(zhuǎn)換成了兩個鏈表求交點的問題。因為此時headA鏈表的尾部是meet,而headB鏈表的尾部也是meet,此時就意味著倆鏈表必會相交,而相交的地方就是入口點,兩鏈表相交正是博主上篇博文中所詳細講解的,這里就不過多強調(diào)了。

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

相關(guān)文章

  • C++實現(xiàn)兩個日期間差多少天的解決方法

    C++實現(xiàn)兩個日期間差多少天的解決方法

    本篇文章用實例說明,在C++中實現(xiàn)兩個日期間差多少天的方法。需要的朋友參考下
    2013-05-05
  • C++ LeetCode1832題解判斷句子是否為全字母句

    C++ LeetCode1832題解判斷句子是否為全字母句

    這篇文章主要為大家介紹了C++ LeetCode1832題解判斷句子是否為全字母句示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2022-12-12
  • C語言冷知識之預(yù)處理字符串操作符詳解

    C語言冷知識之預(yù)處理字符串操作符詳解

    當年學(xué)習(xí)C語言的第一門課就提到過標記(Token)的概念,不過,相信在多年之后你再次聽到這個術(shù)語時會一臉懵逼,比如我。因此特地翻了翻資料,整理下來這些筆記,希望對大家有所幫助
    2022-11-11
  • OpenGL繪制Bezier曲線的方法

    OpenGL繪制Bezier曲線的方法

    這篇文章主要為大家詳細介紹了OpenGL繪制Bezier曲線的方法,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-04-04
  • Linux下C語言修改進程名稱的方法

    Linux下C語言修改進程名稱的方法

    這篇文章主要介紹了Linux下C語言修改進程名稱的方法,涉及Linux下使用C語言操作進程的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下
    2015-07-07
  • C++深入探究不同的繼承體系

    C++深入探究不同的繼承體系

    繼承是C++面向?qū)ο缶幊讨械囊婚T。繼承是子類繼承父類的特征和行為,或者是繼承父類得方法,使的子類具有父類得的特性和行為。重寫是子類對父類的允許訪問的方法實行的過程進行重新編寫,返回值和形參都不能改變。就是對原本的父類進行重新編寫,但是外部接口不能被重寫
    2022-05-05
  • 淺談C++虛重載操作符 virtual operator= 的使用方法

    淺談C++虛重載操作符 virtual operator= 的使用方法

    下面小編就為大家?guī)硪黄獪\談C++虛重載操作符 virtual operator= 的使用方法。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-01-01
  • 全面了解結(jié)構(gòu)體、聯(lián)合體和枚舉類型

    全面了解結(jié)構(gòu)體、聯(lián)合體和枚舉類型

    下面小編就為大家?guī)硪黄媪私饨Y(jié)構(gòu)體、聯(lián)合體和枚舉類型。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-07-07
  • C++程序代碼優(yōu)化的方法實例大全

    C++程序代碼優(yōu)化的方法實例大全

    優(yōu)化是一個非常大的主題,本文并不是去深入探討性能分析理論,算法的效率,這篇文章主要給大家介紹了關(guān)于C++代碼優(yōu)化的相關(guān)資料,需要的朋友可以參考下
    2022-03-03
  • C++中vector容器的常用操作方法實例總結(jié)

    C++中vector容器的常用操作方法實例總結(jié)

    vector容器一般被用作創(chuàng)建動態(tài)數(shù)組,動態(tài)數(shù)組就像Python中的list結(jié)構(gòu)一樣,可以比普通數(shù)組擁有更豐富操作方法,下面就為大家整理了一些最常用的操作:
    2016-05-05

最新評論