pointers - リンクリストの終わりを見つける

Question

面接の質問を調べていると、「リンクリストに終わりがあるかどうか（つまり、リストがサイクルではないかどうか）をどうやって知ることができますか？」に出くわしました。それは解決策を与えます（一度に1つと2つのノードをトラバースし、ポインターが常に等しいかどうかを確認します）。

開始したポインターを保持して、それをトラバースしているときに、そのポインターをもう一度ヒットするかどうかを確認することはできませんか？それともうまくいきませんか？

Answer 1

それは機能しません。リンクリストには、最初のポインタを含まないサイクルが含まれている可能性があります。

リンクリスト内のノードは、他の複数のノードによってリンクされる可能性があることに注意してください。

Answer 2

1つは一度に1つのノードでリストをトラバースし、もう1つは一度に2つのノードでリストをトラバースする必要がある2つのポインターを取ります。いずれかの時点でそれらが互いに出会う場合（両方のポインターが同じノードを参照する場合）、これは循環リンクリストを意味し、終わりはありません。

Answer 3

Couldn't we just keep the pointer that we start at and see if 
while traversing it, we ever hit that pointer again?

いいえ。以下のケースを参照してください。リストの開始ノードに到達することなく、ループをトラバースするだけです。

ループがあるかどうかを確認する別の方法：

リストを逆にして、最初のノードを思い出すと、最初のノードに戻るとサイクルがあることがわかります。このソリューションは効率的ですが、リストを変更するため、マルチスレッドアプリケーションには適していません。