リンクリスト検出アルゴリズムのループについて読んだのです が、疑わしいです
1）「会議要素」の検出方法。たとえば、次の場合-会議が3番目の要素にあることを検出する方法は？
2）リストの長さを検出する方法（上記の場合-6）
実行時間O（n）、メモリO（1）の両方の質問。
質問する
2661 次
3 に答える
9
亀のうさぎアルゴリズム（フロイドの循環検出）を使用して、与えられたリストからループを見つけることができます。
つまり、1つは速度1で、もう1つは速度2の2つのポインターを移動すると、リンクリストにループがある場合にそれらのポインターが一致することになります。なんで？トラックを運転している2台の車について考えてみてください。速い車は、常に遅い車を追い越します。
ここで注意が必要なのは、ループの開始点を見つけることです。例えとして、2人がトラックを走り回り、1人がもう1人の2倍の速さで走っているところを想像してみてください。彼らが同じ場所から始めた場合、彼らは次にいつ会うのでしょうか？彼らは次のラップの開始時に次に会います。
したがって、ループを特定した後、n1をHeadに戻し、n2をMeetingPointに保持し、両方を同じペースで移動すると、LoopStart（Meeting Element）で合流します。
次に、長さを見つけるために、n1を頭に戻すときに、長さ変数を定義します。ここで、移動ごとに長さ変数をインクリメントします。LoopStartを識別した後、n1 ptrをそのままにして、移動ごとにn2ptrとincの長さを移動します。n2-> next == n1の場合、長さを返します。
これには、実行時間O（N）、スペースの複雑さO（1）があります。
于 2012-09-06T12:11:56.630 に答える
0
フロイドの循環検出アルゴリズムを使用する場合、高速参照と低速参照は3番目の要素ではなく、4番目の要素で一致します。それらの位置は（1,2）から始まり、次のように移動します：（1,2）->（2,4）->（3,6）->（4,4）。
サイクルが正確にどこにあるかを見つけるには、O（n）時間だけでなくO（n）スペースも必要だと思います。
于 2012-09-06T11:31:31.343 に答える
-1
O（1）の作業メモリーだけを使ってO（ n ）時間でこれを行うことはできないと思います。
「会議要素」（サイクルの開始）にはnの異なる候補がありますが、O（1）メモリでは、それらの固定数のみを記録できます。構造を何度も回ることができれば問題はありませんが、各トラバーサルで固定数のノードしかチェックできない場合は、構造をn回トラバースする必要があり、合計時間はO（n² ）になります。 。
簡単な解決策は、O（1）メモリ要件をあきらめることです。ループを1回回って、重複するエントリに到達するまで、ノードへのポインタをハッシュテーブルに格納します。予想時間O（n）、メモリ使用量O（n）。
于 2012-09-06T11:33:45.843 に答える