list - Linked List のループ検出

Question

関連セクションでこの質問を見て、いくつかの議論を経た後、最も一般的な解決策はウサギとカメのアルゴリズムであることがわかりました。しかし、私が見たもう1つの提案された解決策（これは私がやったことです）は、ブール変数のように、アクセスしたノードを追跡するNodeクラスの3番目のインスタンス変数を含めることです。これは有効な解決策と見なされますか？

Answer 1

あなたの解決策は、それが仕事を成し遂げるという意味で、間違いなく有効なものです。

ただし、ループの検出の問題は通常、O(1)追加のメモリを使用するという追加の制約で定式化されます。うさぎと亀のアルゴリズムはこの制約を満たしますが、アルゴリズムは満たしていませんO(N)。ノードごとのブール値を格納するために追加のメモリが必要です。