在Floyd的循環查找中跳過多個節點算法

今天我讀到了Floyd在鏈表中檢測循環的算法。我只是想知道，如果我們跳過多個節點（比如說2）更快的循環檢測會不會更好？在Floyd的循環查找中跳過多個節點算法

例如：

fastptr=fastptr->next->next->next.

注意副作用將同時改變fastptr予以考慮。

如果跳過的次數超過1，則可能會錯過最早時刻的循環檢測。 – leppie

@leppie，你能舉一個這樣的例子嗎？ –

更糟的是，你可能根本沒有察覺到循環。考慮一個長度爲6的環路，其中當龜位於節點1時，野兔在節點0處。如果野兔爲龜的每一步移動三步，則隨後的龜/野兔位置爲2/3,3/0,4/3，5/0，0/3,1/0,2/3無限期，並且永遠不會檢測到循環的存在。 – ottomeister

您的建議仍然正確，但它不會改變算法的速度。如果採取在wiki看看烏龜和野兔算法：

在算法中的關鍵結論是，對於任何整數我≥μ和k ≥0，X _我 = X _{I +Kλ}，其中λ是要找到的循環的長度，μ是循環的起始位置。特別是，當i =kλ≥μ時，因此，x _i = x _2i。

在加粗部分，你也可以說X _我 = X _3I，或任何其他係數，但主要觀點是找到我，它不是用多少跳你很重要會發現它，並且算法的順序取決於的位置i。

2012-06-12 07:07:50

回答