data-structures - リンクされたリストが循環しているかどうかを確認する

Question

ここで亀とウサギ（遅いランナーと速いランナー）アルゴリズムについて読んだところですが、なぜそれが最適なソリューションと見なされるのかよくわかりません。

これを行うのに時間がかからないでしょうか:

• ルート ノードを保存

• リンクされたリストを移動する

• 新しいノードごとに、それがルート ノードかどうかを確認します。

Answer 1

循環リストは、必ずしも先頭に接続する必要がないことに気付きました。真ん中のどこかにループがあるだけです。そのため、2 つの「ランナー」が必要になります。

しかし、「ヘビが自分の尻尾を食べる」タイプのリンクリストを明示的にチェックしている場合は、前に提案したように、ポインターとルートノードが等しいかどうかをチェックするだけで十分です。