在單個鏈表中檢測週期是一個衆所周知的問題。我知道這個問題在互聯網上已經被問及數十億次了。我之所以再問這個問題，是因爲我想到了一個我在其他地方沒有遇到的解決方案。 （我承認我還沒有深入搜尋）。在單向鏈表中檢測週期
我的解決辦法是：
給定一個鏈表指針一些節點，打破節點之間的鏈路和節點 - >下（）; 然後從node-> next（）開始並遍歷，直到你到達一個結束點（這意味着沒有循環）或者直到到達節點，這意味着有一個循環。
上面的解決方案有什麼不對嗎？
注：不要加入鏈接回一旦你完成。
，將工作，檢測完整週期（即週期，其週期的整個列表的），例如：
A -> B -> C -> D -> A
但是，如果我們在列表中的循環別的地方？
例如，
A -> B -> C -> D -> E -> C
我看不到你的算法將檢測週期在這種情況下。
請記住，要檢測第一種情況，我們甚至不需要中斷鏈接。我們可以遍歷該列表並繼續比較每個節點的next鏈接和head元素，以查看我們是否在開始時重新開始（或者結束）。
我想最簡單的方法（不一定是最好的，但每個人都應該知道如何用Java在幾行代碼中實現的方法）是構建一個節點的哈希集，開始添加它們直到找到一個你已經看過。雖然需要額外的記憶。
如果你可以標記節點，標誌着開始，直到你找到一個你之前標記（散列圖基本上是一個外部標記）。
並檢查常用圖形理論書籍...
你不允許斷開了鏈接，即使你加入回底。如果其他程序同時讀取列表，該怎麼辦？
該算法在處理時不得損壞列表。
大多數解決方案都表明，兩種不同速度的「跑步者」是最好的解決方案。會發生O（n），我的解決方案O（n）也是？ –
我沒有看到任何破壞鏈接的理由，只是將節點當作哨兵。一個問題：如果節點是a，那麼你的算法就不能在a-> b-> c-> d-> e-> c上工作。你的算法只會檢測最後一個節點指向第一個節點的循環。 –
如果循環不是全局的，則這不起作用。例如：'a - > b - > c - > b - > c - > b - > c - > b - > ...'永遠不會返回到a。 –