鏈接列表循環檢測算法

我在網上閱讀了一些關於如何查找鏈表中是否存在循環的採訪問題，解決方案（Floyd的循環查找算法）有兩個指針，一個比另一個快兩倍，並檢查他們是否再次見面。鏈接列表循環檢測算法

我的問題是：爲什麼我不能只固定一個指針，只要每次向前移動另一個指針1步？

2011-09-13 Derek Li

如果有人很好奇，算法有一個更快的修改：http：//www.siafoo.net/algorithm/11 – Dave

因爲第一個（非移動）指針可能不在循環內，所以指針永遠不會相遇。（請記住，循環可能只包含部分列表。）

2011-09-13 08:15:15

這是清除它。謝謝大家，因爲我只能標記一個正確的答案，我會標記最早的答案。 –

因爲循環可能不包含第一個指針指向的元素。例如，如果第一個指針指向元素1並且鏈表後面有一個循環（1-> 2-> 3-> 4-> 2），那麼您的算法將不會檢測到它。

2011-09-13 08:15:37 quasiverse

只是刪除了一些小錯別字，所以我可以在一週內以良心良心給你50+（因爲你錯過了被接受幾秒鐘）。 – DaveFar

@DaveBall哇。謝謝。我很高興你注意到了。 ;） – quasiverse

因爲可能不是完整的linkedList在循環內。

對於鏈表套索檢測算法，則需要兩個指針：

enter image description here

只要第一個指針是在牛仔是，沒有檢測到循環。但是如果你逐步向前移動，它最終會進入循環。

順便說一句，套索是圖論的終點技術，牛仔不是。

2011-09-13 08:29:06 DaveFar

+33

+1爲牛仔。 – Heinzi

yeeeeeeeehaw :) – DaveFar

+1對於@quasiverse的體面態度以及牛仔 – Basic

回答