0

2 つのポインターとサイクル検出アルゴリズムを使用できることはわかっていますが、先週のインタビューで、 を使用して同じことを行うように求められましたO(N) space Complexity。どのように進めることができますか?

4

1 に答える 1

1

詳細な実装については、この投稿 (リンクされたリストに 2 つのメモリ ロケーションのみを使用するサイクルがあるかどうかを判断する方法) をお読みください。

基本的には 2 つのポインターを保持します。どちらも最初はリンク リストの先頭を指します。列挙ごとに、最初のポインターを 1 ノードずつ進め、もう 1 つのポインターを 2 つ進めます。ある時点でこれら 2 つのポインターが再び同じノードに到達すると、循環が検出されます。

あなたの説明から、あなたはこのアルゴリズムを知っていると思います。リンクされたリスト自体が占めるスペースが考慮されていない場合、これはO(1)スペースで機能します。そして、それだけのスペースを考慮しても、それはまだO(n)です. (スペースの複雑さが唯一の懸念事項である場合、明らかに悪いアルゴリズムが存在します。)

于 2013-07-05T12:46:56.567 に答える