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

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)的入口點相遇?。?!

環(huán)形鏈表 II

環(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)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C++深度探索運算符重載和返回值優(yōu)化

    C++深度探索運算符重載和返回值優(yōu)化

    這篇文章主要介紹了C++運算符重載及編譯器返回值優(yōu)化,C++當(dāng)中除了函數(shù)可以重載之外,其實運算符也是可以重載的,下面一起來詳細(xì)了解吧
    2022-04-04
  • C語言新手入門之格式化輸出和變量類型

    C語言新手入門之格式化輸出和變量類型

    這篇文章主要給大家介紹了關(guān)于C語言中格式化輸出和變量類型的相關(guān)資料,文中的教程非常適合新手零基礎(chǔ)的朋友們參考學(xué)習(xí),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。
    2018-03-03
  • 帶你了解如何用C++合并兩個有序鏈表

    帶你了解如何用C++合并兩個有序鏈表

    這篇文章主要介紹了c++ 如何合并兩個有序鏈表,小編感覺這篇文章還不錯,希望能幫助大家更好的理解和學(xué)習(xí)C++,感興趣的朋友可以了解下
    2021-08-08
  • C語言 單向鏈表的增刪查改快速掌握

    C語言 單向鏈表的增刪查改快速掌握

    單向鏈表特點是鏈表的鏈接方向是單向的,訪問要通過順序讀取從頭部開始。鏈表是使用指針構(gòu)造的列表,是由一個個結(jié)點組裝起來的,又稱為結(jié)點列表。其中每個結(jié)點都有指針成員變量指向列表中的下一個結(jié)點,head指針指向第一個結(jié)點稱為表頭,而終止于最后一個指向nuLL的指針
    2021-11-11
  • 解析在WTL下使用雙緩沖的實現(xiàn)方法

    解析在WTL下使用雙緩沖的實現(xiàn)方法

    本篇文章是對在WTL下使用雙緩沖的實現(xiàn)方法進行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • C++浮點數(shù)在內(nèi)存中的存儲詳解

    C++浮點數(shù)在內(nèi)存中的存儲詳解

    大家好,本篇文章主要講的是C++浮點數(shù)在內(nèi)存中的存儲詳解,感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下
    2022-01-01
  • C語言編程中借助pthreads庫進行多線程編程的示例

    C語言編程中借助pthreads庫進行多線程編程的示例

    這篇文章主要介紹了C語言編程中借助pthreads庫進行多線程編程的示例,文中的示例環(huán)境為Windows系統(tǒng),需要的朋友可以參考下
    2015-11-11
  • String類的寫時拷貝實例

    String類的寫時拷貝實例

    下面小編就為大家?guī)硪黄猄tring類的寫時拷貝實例。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-01-01
  • C++ 實現(xiàn)帶監(jiān)視哨的順序查找算法

    C++ 實現(xiàn)帶監(jiān)視哨的順序查找算法

    這篇文章主要介紹了C++ 實現(xiàn)帶監(jiān)視哨的順序查找算法,本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-03-03
  • 一文帶你了解C++中deque的使用

    一文帶你了解C++中deque的使用

    C++中的deque是一種雙端隊列,可以在隊列的前端和后端進行插入元素和刪除操作,同時可以視作一個長度不定的數(shù)組,支持高效的插入和刪除操作。本篇文章將深入探討C++中的deque的使用,感興趣的可以了解一下
    2023-05-05

最新評論