跟蹤檢測鏈表中的循環

Question

因此，如何檢測鏈表中的循環有幾個問題。 Here就是一個例子。我的問題是，爲什麼所有這些算法都使用兩個指針？難道你不能只用一個指針循環，並將節點標記爲已訪問過，並且當你到達一個已經訪問過的節點或者到達鏈表末尾（next = null）時，那麼你知道沒有循環？

Answer 1

這是因爲

紀念節點所訪問

你需要在節點或者額外的空間，自己做，或輔助數據結構，它的大小將與的增加列表，而雙指針解決方案只需要足夠的額外空間來存放一個指針。

[編輯補充：] ...也許，也是因爲雙指針解決方案是巧妙的和人們喜歡巧妙的解決方案。