C語言?推理證明帶環(huán)鏈表詳細(xì)過程
什么是帶環(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)形鏈表
給你一個鏈表的頭節(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
給定一個鏈表的頭節(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)文章希望大家以后多多支持腳本之家!