我知道Tortoise和Hare的會議總結了循環的存在，但是如何將烏龜移動到鏈接列表的開頭，同時又將野兔保留在聚會地點，然后一次移動兩個步驟，使它們在循環的起點相遇呢？
3 回答
jeck貓
TA貢獻1909條經驗 獲得超7個贊
這是用于循環檢測的弗洛伊德算法。您正在詢問算法的第二階段-找到一個節點是周期的一部分后，如何找到周期的起點？
在弗洛伊德算法的第一部分中，野兔為烏龜的每一步移動了兩步。如果烏龜和野兔相遇過，就會有一個循環，并且集合點是循環的一部分，但不一定是循環中的第一個節點。
當烏龜和野兔相遇時，我們找到了最小的i（烏龜采取的步數），使得X i = X 2i。令mu代表從X 0到循環開始的步數，令lambda代表循環的長度。然后，i = mu + a lambda，而2i = mu + b lambda，其中a和b是整數，表示烏龜和野兔在循環中跑了多少次。從第二個方程中減去第一個方程可得出i =（ba）* lambda，因此i是lambda的整數倍。 因此，X i + mu = X mu。X i代表烏龜和野兔的交匯點。如果您將烏龜移回起始節點X0，然后讓烏龜和野兔以相同的速度繼續前進，經過多步，烏龜將達到X mu，野兔將達到X i + mu = X mu，因此第二個相遇點表示烏龜的開始周期。
-
qq_慕雪7282832看了這么多 終于有個能看懂的了
眼眸繁星
TA貢獻1873條經驗 獲得超9個贊
參考此圖片：
慢速指針在會議之前經過的距離 = x + y
在會議之前fastPointer行駛的距離 =（x + y + z）+ y = x + 2y + z
由于fastPointer行駛過程中雙 slowPointer的速度，時間是恒定的，當到達會合點兩種。
因此，通過使用簡單的速度，時間和距離關系2（x + y）= x + 2y + z => x + 2y + z = 2x + 2y => x = z
因此，通過將slowPointer移動到鏈接列表的開頭，并使slowPointer和fastPointer一次移動一個節點，它們的覆蓋距離相同。
它們將到達循環列表中循環開始的位置。
添加回答
舉報
0/150
提交
取消