個人 可以做網(wǎng)站備案嗎seo超級外鏈
各位友友們,好久不見呀!又到了我們相遇的時候,每次相遇都是一種緣分。但我更加希望我的文章可以幫助到大家。下面就來具體看看今天所要講的題目。
文章目錄
- 1.環(huán)形鏈表
- 2.環(huán)形鏈表II
1.環(huán)形鏈表
題目描述:https://leetcode.cn/problems/linked-list-cycle/description/
這道題目呢,現(xiàn)階段使用C語言的最優(yōu)方案就是使用快慢指針的方法。下面就讓我給大家介紹如何使用快慢指針的方法來解決這道題目。
我們假設讓快指針一次走兩步,慢指針一次走一步。下面我將用圖來更直觀描述此題的邏輯。
1.當fast指針準備進環(huán)時,slow指針才走了fast指針的一半。
2.當slow指針準備進環(huán)時,fast指針已經(jīng)在環(huán)內轉了幾圈了。
3.當slow指針進環(huán)時,fast指針就開始追擊slow指針
走到這里,這道題目實際上就變成了追擊問題。當fast指針追上slow指針時,說明該鏈表是帶環(huán)鏈表。反之則為不帶環(huán)鏈表。
思路清晰,下面請看代碼實現(xiàn):
bool hasCycle(struct ListNode *head) {struct ListNode* fast = head,*slow = head;while(fast && fast -> next){fast = fast -> next ->next;slow = slow ->next;if(slow == fast){return true;}}return false;
}
其實,這道題目還有兩個問題:
1:為什么兩個指針一定會相遇?有沒有可能會錯過,或者永遠追不上?
2:當slow走一步時,可不可以讓fast指針一次走3步或者其它的步數(shù)呢?
下面就根據(jù)以上兩個問題分別討論一下
1.我們假設slow進環(huán)時,slow跟fast的距離為N
當fast開始追擊slow的時候,它們之間的距離變成N-1、N-2…直到0。說明它們每追擊一次,它們之間的距離就縮小1,而距離為0時則它們相遇。
2.我們假設分析一下slow指針一次走一步,fast指針一步走三步的情況
1)當slow走了三分之一時,fast指針已經(jīng)準備開始進環(huán)了。
2.當slow指針走了三分之二時,fast指針已經(jīng)在環(huán)內轉了幾圈了。
3.當slow指針準備進環(huán)時,fast指針又在環(huán)內轉了不知道多少圈
我們還是假設slow指針進環(huán)時,fast指針和slow指針的距離為N
當fast指針開始追擊slow指針時,它們的距離變化為:N-2、N-4、…
到這里,就有兩種情況產(chǎn)生:
①當N為偶數(shù)時:則最終的距離會變成0,則說明他們相遇
②當N為奇數(shù)時:則最終的距離會變成-1,則說明它們錯過了,進入新一輪的追擊。
我們假設C代表環(huán)的長度,那么新一輪追擊的距離就變成C-1了。
這里又有兩種情況:
1)當C-1為偶數(shù)時:則來到第①這種情況,最后會追上。
2)當C-1為奇數(shù)時:則來到第②這種情況,它們將永遠錯過,無法相遇,陷入死循環(huán)。
那么當C為偶數(shù),N為奇數(shù)時,則說明它們無法相遇,是否會有這種情況發(fā)生呢?
我們假設當slow指針準備進入環(huán)時,slow指針走過的距離為L,fast指針走過的距離為L + xC + C-N。因此,我們會產(chǎn)生一條等式:
3L = L + xC + C - N 化簡就變?yōu)? 2L = (x+1)*C - N
偶數(shù) = (x+1) × 偶數(shù) - 奇數(shù) ? 這顯然等式不成立,則說明不可能存在C為偶數(shù),N為奇數(shù)的這種情況,即不存在追不上的這種情況。
討論完fast指針走三步的情況,那么fast指針走n步的情況也跟以上的方法類似,只不討論的過程會更加繁瑣一點。
2.環(huán)形鏈表II
題目描述:https://leetcode.cn/problems/linked-list-cycle-ii/description/
這一道題目的解法也是用快慢指針這一方法。
想要找到入口點,最簡單的辦法就是讓一個指針從頭開始走,一個指針從fast指針和slow指針相遇的位置開始走,當兩個指針相遇時,則找到入口點。
代碼展示:
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fast = head,*slow = head;while(fast && fast->next){fast = fast -> next -> next;slow = slow -> next;//如果相遇了if(slow == fast){struct ListNode* meet = slow;while(meet != head){meet = meet -> next;head = head -> next;}return meet;}}return NULL;
}
現(xiàn)在又有一個問題:為什么入口點就在那個地方呢?下面就對其進行證明:
假設從頭開始走到入口點的距離為L,slow進環(huán)走的距離為N,環(huán)形鏈表的長度為C
那么當fast指針和slow指針相遇時:
fast指針走過的路程為: L + xC +N (x>=1的整數(shù))
slow指針走過的路程為: L + N
因此我們得到一條等式: 2(L + N) = L + xC +N (x>=1)
化簡得: L = x*C - N,便于觀察,我們可以將等式變?yōu)?L = (x-1)*C + C - N
因此,不管x的值為多少,只需讓相遇點多走C - N的距離,就能說明head指針和meet指針相遇,從而找到入口點。
今天的分享就到這里啦,如果感覺內容不錯,記得一鍵三連噢。創(chuàng)作不易,感謝大家的支持,我們下次再見!ヾ( ̄▽ ̄)ByeBye