各位友友們，好久不見呀！又到了我們相遇的時候，每次相遇都是一種緣分。但我更加希望我的文章可以幫助到大家。下面就來具體看看今天所要講的題目。

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)作不易，感謝大家的支持，我們下次再見！ヾ(￣▽￣)Bye_Bye