3

特定のリンクリストでループの開始ノードを見つける方法は？これをサイクルポイントと呼びましょう

これまでのところ、私は次のことを理解しています（低速/高速ポインタを使用）：

  1. リストにループされていないサイズの部分があると仮定しますk
  2. ゆっくり動くkステップ
  3. 速い動き2kステップ
  4. 速いのは（2k-k）=遅いのkステップahead
  5. 遅いのはループの始まりです。としても知られているCycle point
  6. 速いとは、この時点でのポインタからの(LOOP_LENGTH - k)ステップまたは遅いポインタです。behindCycle point
  7. 1ステップのスロームーブごとに、ファストムーブは2ステップ、スローは1ステップずつ増加します。
  8. したがって、(LOOP_LENGTH - k)ゆっくりと衝突するためには速いステップが必要です
  9. これは私が理解していないステップです 。この衝突点では、両方のノードがkループの前からのステップになります。
  10. 衝突点が見つかったら、1つのポインターをリストの先頭に移動します。
  11. 次に、衝突するまで1ステップ/回転の速度で両方のポインターを移動します。それらが両方とも出会うノードはループの始まりであり、したがってCycle point

誰かが私にステップ9以降を説明してもらえますか？

ありがとう

編集：

私が指摘したいことの1つは、ループ内に入ると、高速が低速ポインターを追い抜くことは決してないということです。彼らは衝突します。その理由は次のとおりです。低速はiで、高速はi-1であると想定しています。それらが移動すると、slow => i+1とfastもi+1になるため、衝突します。または、低速はiで、高速はi-2です。次の動き、遅い-> i + 1; 高速：i。次の動き、遅い-> i + 2、速い：i + 2、したがって再び衝突。とても速いので遅い追い越しはできません。ループ内で一度だけ衝突します！

4

2 に答える 2

3

あなたの6.は間違っています、速いポインターはまだその時のサイクルポイントにある遅いポインターからkステップ離れています。ただし、離れた場所ではなく、前または後ろで使用することをお勧めします。さらに、より小さい、大きい、または等しい場合があります。kloop_length

したがって、高速ポインタはk、ループポイントに到達したときに低速ポインタよりも一歩進んでいます。ループポイントは、あなたの想定ではk、開始後のステップです。ここで、ループで測定すると、高速ポインターはk % loop_lengthループポイントの一歩先にあります。右？の場合k = some_n * loop_length + r、高速ポインタはrループポイントよりも一歩進んでいます。つまり、一r := k % loop_length歩進んでいます。

しかし、それは、ループに沿って、遅いポインターが速いポインターよりも一loop_length - r歩進んでいることを意味します。結局、これはループです。したがって、loop_length - r追加の手順の後、高速ポインタは低速ポインタに追いつきます。ステップごとに、遅いポインターが離れ、速いポインターが2ステップ近くに移動します。

ですから、私たちは知りませんk、私たちは知りません、loop_lengthまたはr、私たちは知っているだけm = k + loop_length - r = some_n * loop_length + r + loop_length - r = (some_n+1) * loop_lengthです。m2つのポインターの合流点までの合計ステップ数は、ループ長の倍数です。

だから今、私たちは最初からやり直し、最初に新しいポインターを置き、それが速いものと出会ったところで遅いものをm新しいものの一歩先に進めます。新しいポインターとスローを同じ速度で、毎回1ステップずつ移動し、サイクルポイントでそれらが出会うようにします。新しいポインターがサイクルポイントに達したとき、2番目のポインターはまだ一m歩進んでいるため、つまり、m % loop_length == 0ループに沿って前進します。このようにして、私たちは何kであるか（私たちは常に歩数を数えます）、そしてサイクルポイントを見つけます。

そしてloop_length、2つがもう一度会うまで、もう一度ループに沿って進むことによって見つけます。

于 2012-07-21T11:18:49.283 に答える
0

うーん..この種の問題は、あなたが顔を合わせて話しているのでない限り、説明するのは難しいです。やってみます。

まず、ステップ6で：高速ポインターはk円の点から離れている必要があると思います。

しかし、それはすべて残してください。現在、2台の車があります。遅い車の2倍の速度の速い車。

速い車がk円の点から離れた円形の軌道で始まると仮定します。

そして、遅い車はサークルポイントから始まります。

今、私は両方の車がk円点の前に距離を置いて出会うと言っています。

なんで？最初は速い車がk円の点から離れているからです。n速い車は、最初にサークルを完了するときに距離をカバーします。これで、高速車は再び円点からkの距離になります。しかし、遅い車はn/2円点から離れています。

これで、高速車は、円点の前の距離にn-2k到達するために、より多くの距離をカバーする必要があります。kそして、遅い車は出発点の前のn/2 - k = (n-2k) / 2距離に到達するために距離をカバーしなければなりません。。そして速い車は遅い車の2倍の速度です。kWhich is exactly half the distance of the path to be covered by the fast car

kしたがって、明らかに、それらは円点から前に距離を置いて出会うでしょう。

于 2012-07-21T10:59:14.270 に答える