0

この問題には本当に洗練された解決策がありますが、私は最大の部分を理解していません-Sをリストの最初に戻した後、SとFがループの開始から同じ距離にあるのはなぜですか？彼はそれを「証明」するためにいくつかの数学をしますが、それは私にはまったく意味がありません。これをよりよく理解するための助けをいただければ幸いです。ありがとう！

4

2 に答える 2

1

n問題を組み立てるために、開始を過ぎてノードを開始するノードループmがあり、低速ポインターS（各ステップに1ノード）と高速ポインターF（各ステップに2ノード）でそれを歩いていると仮定します。簡潔にするために、と仮定しm < nますが、それほど重要ではありません（モジュラー演算を実行するだけです）。

重要なのは、SとFがノードでオーバーラップすることを理解することn - mです。この記事で行われた計算は、確かに理解するのが少し難しく、奇妙に一般化されていないようですn。これがはるかに簡単になるかどうかはわかりませんが、試してみます。

Sがループの開始時に開始し、Fがループkの開始を過ぎてノードを開始し、ループのウォークを開始するとします。タイムステップxで、Sはループの開始を過ぎたノードxになり、Fはループの2x + k開始を過ぎたノードになります。もちろん、Fがループの開始を通過するまでFはSを追い越しません。その時点で、Fは開始を(2x + k) - n = 2x - (n - k)過ぎたノードであると同等に説明できます。

xここで、「 SとFはどのステップでオーバーラップしますか？」と尋ねます。これは、Sの位置がFの位置と等しい場合、つまりx = 2x - (n - k)、または（いくつかの単純な代数を使用して）、x = n - kです。したがって、両方のポインターはn - k、ループの開始を過ぎたノードになります。

元の問題に戻ると（両方のポインターはリストの先頭から始まります）、Sが開始に達するまでに（mステップ単位で）、Fは2mステップを移動してmいるため、ループの開始を過ぎたノードになります（2m - m = m）。上記に置き換えkてmください。続行すると、ポインタF（およびS）がn - mループの開始を過ぎたノードである場合にノードがオーバーラップすることがわかります。したがって、Sを最初に戻すと、FとSの両方mがループの最初に戻るための手順を実行します。

これが役立つかどうか教えてください。

于 2012-09-15T19:39:07.187 に答える
0
  1. 2つのポインター（fとs）を取ります。
  2. リンクリストヘッドから両方のポインタを開始します。f（速い）をs（遅い）の2倍の速度でトラバースします。つまり、fは2回ジャンプし、sは1回ジャンプします。
  3. 彼らが会うかどうかを確認してください。
  4. それらが会う場合は、sがリンクリストの先頭を指すようにし、fの値を変更しないでください（fは現在それらの会議ノードを指しているため）
  5. 次に、両方のポインタ速度を等しくし、1つのノードのみを移動するようにします。
  6. それらが出会うポイントは、ループの開始になります。（これを取得するには、図を描くか、上記の投稿を理解してください。

あなたがこれを手に入れたら私に知らせてください。喜んでお手伝いさせていただきます。

于 2012-09-16T13:46:39.510 に答える