問題描述：
給定一個鏈表，判斷鏈表中是否有環，
首先介紹一下快慢指標：
我們定義兩個指標，一快一慢，慢指標每次只移動一步，而快指標每次移動兩步，
來看以下例子：
在環形鏈表問題中，我們用slow和fast指向鏈表的開始，slow一次走一步，fast一次走兩步，若不帶環，fast就會為空，帶環，fast就會在環內追上slow
1.我們先來證明為什么slow和fast一定會在環中相遇，
- fast先進環，這時slow走了入環前距離的一半，
- 隨著slow進環，fast在環內走了一段，但走了多少跟環的大小有關，
- 假設slow進環時，與fast之間的距離是N，fast開始追slow，slow每次往前走一步，fast往前走兩步，所以fast和slow的距離變化：
N -> N-1 -> N-2 … 1 -> 0
每追一次，距離就減1，他們之間的距離減到0的時候就是相遇的點，
那么如何求環的入口點呢？
追上相遇的程序中：
- slow走的距離：L+X
fast走的距離：L+N* C+X (N>=1)
(N是相遇前，fast在環內走的圈數) - 2*（L+X) = L+N* C+X
得到：L=(N-1)* C+C-X - 其中，(N-1)* C相當于從相遇點又走回到相遇點，沒有變化， C-X 相當于從相遇點到相交點（順時針）的距離，
結論： 一個指標從鏈表起始位置運行，一個指標從相遇點位置繞環，每次都走一步，兩個指標最侄訓在入口點的位置相遇，
代碼實作：
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow=head,*fast=head;
while(fast && fast->next)
{
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;
}
或者我們可以轉換成鏈表相交的問題，即令相遇點的下一個結點為另一個鏈表頭，這里不再細講，
延伸問題：證明fast一次走n步時，即n>2時不一定會在環中相遇，
假設slow一次走1步，fast一次走3步，slow進環后，fast和slow之間的距離為N，fast開始追slow，
他們之間的距離變化如下：
-
N是偶數：
N -> N-2 -> N-4 … 2 -> 0
N是偶數時可以追上 -
N是奇數：
N -> N-2 -> N-4 … 1 -> -1
N是奇數時，將會錯過
如果N是奇數，距離變為-1，即意味著他們之間的距離變為C-1(C是環的長度）
如果C-1也是奇數，那么就永遠追不上了，
如果C-1是偶數，就可以追上，
假設slow一次走1步，fast一次走n步的推導程序與之類似，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/335546.html
標籤：其他
上一篇：【Linux系列筆記】---------g++/gcc應該這樣學！（六）
下一篇：Dart對串列進行排序