當使用快慢的方法時，在一個有回圈的鏈表中。這兩個指標將在一個節點處相遇。然后將兩個指標中的一個指向頭節點，另一個指標停留。接下來，讓他們每次都走一步。最后，他們將在回圈的第一個節點相遇。我想知道為什么。謝謝。我的意思是“回圈中的第一個節點”
uj5u.com熱心網友回復：
您將通過手動解決幾個示例來理解這一點：
1 -> 2 -> 3 -> 4 (suppose 4 is connected to 2)
- (fast)
(slow)
[start moving]
1 -> 2 -> 3 -> 4
-
1 -> 2 -> 3 -> 4
-
1 -> 2 -> 3 -> 4
-
Now the have met. Let's declare 2 pointers @ and # pointing to the head and the node where they met respectively
1 -> 2 -> 3 -> 4
@
#
1 -> 2 -> 3 -> 4
@
#
This is obviously the start of the cycle.
第一個觀察：如果有一個回圈慢和快就會相遇。這是他們采取的步驟長度的結果。2 的每一個倍數都可以被 1 整除。
第二個觀察：在回圈的情況下，慢速和快速相遇點在回圈內。原因很明顯，fast 不會退出回圈，所以這就是他們相遇的地方。
現在，假設從頭到回圈開始的距離是A，從回圈開始到慢速和快速相遇的節點是B。可以說，慢的已經走到A B了快的地方。在此期間快速旅行了多少？2A 2B，因為它以雙倍速度移動。
現在，讓我們找到另一種關于快速行駛距離的公式，它可以幫助我們解決這個方程。我們可以說 fast 已經從回圈的開始到回圈A的開始加上從回圈的開始到會合點B加上從會合點到鏈表的結尾，我們稱之為C，再次從回圈的開始到匯合點B。即A B C B等于A 2B C，其中C是從會合點到鏈表末尾的距離。希望沒有插圖就有意義。
總結到這一點：
A: dist from start of the list to the start of the cycle
B: dist from start of the cycle to the meeting point of slow and fast
C: dist from meeting point to the end of the list
slow has traveled: A B
fast has travelled: 2A 2B (because it moves at double speed)
We can also say fast has traveled: A B C B = A 2B C
讓我們將 fast 移動的距離的這兩個運算式等同起來，并希望求解 A，即從頭到回圈開始的距離。
A 2B C = 2A 2B
A = C
這實際上意味著從頭到回圈開始的距離，即A，等于會合點到鏈表末尾的距離，即C。
如果這是真的，我們可以運行 2 個指標，a并且b，一個來自頭部，一個來自會合點。當b到達鏈表的末尾時，a就是回圈的開始。但既然有一個回圈b就永遠不會走到盡頭。我們創造了一個條件，當b == a我們找到回圈的開始時。這是有效的，因為最后一個節點之后的下一個節點是回圈的開始。
請注意我的解釋：方程式并不完全準確。在長鏈表和非常小的回圈的情況下，fast 可能會移動多個BandC直到 slow 遇到它。所以，A 2B C變成A iB iC B。但這不會改變最終結果。
順便說一下，如果您想進一步閱讀，這就是Floyd 的 Hare and Turtoise 演算法。
如果這還不夠清楚，請詢問。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/415936.html
標籤：
上一篇：旋轉正數和負數的基于零的范圍
下一篇：需要了解代碼是如何作業的