TA貢獻1909條經驗 獲得超7個贊
這是用于循環(huán)檢測的弗洛伊德算法。您正在詢問算法的第二階段-找到一個節(jié)點是周期的一部分后，如何找到周期的起點？
在弗洛伊德算法的第一部分中，野兔為烏龜?shù)拿恳徊揭苿恿藘刹?。如果烏龜和野兔相遇過，就會有一個循環(huán)，并且集合點是循環(huán)的一部分，但不一定是循環(huán)中的第一個節(jié)點。
當烏龜和野兔相遇時，我們找到了最小的i（烏龜采取的步數(shù)），使得X i = X 2i。令mu代表從X 0到循環(huán)開始的步數(shù)，令lambda代表循環(huán)的長度。然后，i = mu + a lambda，而2i = mu + b lambda，其中a和b是整數(shù)，表示烏龜和野兔在循環(huán)中跑了多少次。從第二個方程中減去第一個方程可得出i =（ba）* lambda，因此i是lambda的整數(shù)倍。 因此，X i + mu = X mu。X i代表烏龜和野兔的交匯點。如果您將烏龜移回起始節(jié)點X0，然后讓烏龜和野兔以相同的速度繼續(xù)前進，經過多步，烏龜將達到X mu，野兔將達到X i + mu = X mu，因此第二個相遇點表示烏龜?shù)拈_始周期。
TA貢獻1873條經驗 獲得超9個贊
參考此圖片：
慢速指針在會議之前經過的距離 = x + y
在會議之前fastPointer行駛的距離 =（x + y + z）+ y = x + 2y + z
由于fastPointer行駛過程中雙 slowPointer的速度，時間是恒定的，當?shù)竭_會合點兩種。
因此，通過使用簡單的速度，時間和距離關系2（x + y）= x + 2y + z => x + 2y + z = 2x + 2y => x = z
因此，通過將slowPointer移動到鏈接列表的開頭，并使slowPointer和fastPointer一次移動一個節(jié)點，它們的覆蓋距離相同。
它們將到達循環(huán)列表中循環(huán)開始的位置。
舉報