これは、famousハレとタートル法を使用してリンクリストのサイクルを検出する場合の問題ではありません。リンクリストのサイクル検出：網羅的な理論
Hare & Tortoiseメソッドでは、1xと2xの速度でポインタが動作していることを確認して、最も効率的な方法とその順序がO（n）であることを確信しています。
問題は、私は移動速度が斧（回x）とBxの（B回のx）とAであるときに、2つのポインタが常に満たすことが可能であることの証明（証明または反証）を思い付くする必要がありますはAとBが等しくない。ここで、AとBはサイクルが存在するリンクリスト上で動作する2つのランダムな整数である。
これは私が最近出席したインタビューの1つで尋ねられました。私はそれが可能かどうか自分に包括的に証明できませんでした。どんな助けもありがたい。
ループがあり、長さがLであるとします。
簡単場合、それが簡単に、最初に同時に2個の粒子が全体のループの場合を考えるようにするには
最初。これらの粒子は、同じ正の整数の場合にはn*A = n*B (mod L)と同じ位置にあります。nは、再び会うまでのステップ数です。 n=Lを取ると、1つの解決策が得られます（しかし、より小さな解決策があるかもしれません）。したがって、L単位時間後に、粒子Aは、ループの周りに最初に戻るためにループの周りにAのトリップを行い、Bは、ループの周りにBの旅行を開始し、喜んで衝突します。
一般的なケース
彼らは同時にループを入力しないとき、今、何が起こりますか？ Aを遅い粒子、すなわちA<Bとし、時刻mでループに入るとAと入力して、Aがループに入る位置を呼び出すとします（ループ内にあるので、0になるので、ちょうどA*mを差し引いて位置を変更すると、Aはm時間単位の後に移動しました）。その後、Bは既にm*(B-A)の位置にあります（m時間単位の後の実際の位置はB*mです）。したがって、名前が変更された位置はB*m-A*mです。次に、n*A = n*B+m*(B-A) (mod L)のような時刻がnであることを示す必要があります。つまり、我々は再びかかわらず、小さいソリューションがあるかもしれない、十分なk*L>mはトリックを行うことを大きなkためn = k*L-mを取るモジュラー式
(n+m) * (A-B) = 0 (mod L)
への解決策を必要としています。
したがって、はい、常に満たされます。
2つのステップサイズに共通の係数xがある場合：ステップサイズがAxとBxであるとしましょう。次に、元のシーケンスを取得し、x番目の要素ごとに取得するシーケンスを考えてみましょう。この新しいシーケンスには、元のシーケンスの場合にのみサイクルがあり、サイズAおよびBのステップを実行することは、元のシーケンスでサイズAxおよびBxのステップを実行することと同じです。
この減少は、AとBが共起するときにアルゴリズムが機能することを証明することで十分であることを意味します。
仮説はfalseです。たとえば、両方のポインタが偶数サイズの飛躍をする場合、ループも偶数サイズであり、ポインタ間の距離は奇数であり、決して満たされません。
UPDこれは明らかに不可能な状況です。 2つのポインタは同じ点から始まるので、それらの間の距離は常に偶数になります。
しかし、彼らは最初は同じ点から始まることも知っています。 Paul Hankinの議論を考慮すると、あなたのケースは不可能であることは明らかである（AとBの間に共通の素因がある場合、この要因が取り除かれた同等の事例になることができる）。 – 6502
「最初の部分は同じ点から始まることもわかっています」 - リストの最初の非ルフィ部分があると同時にループに入るとは限りません。 –
ああ、それは確かに可能ではないと思う。 –
"この新しいシーケンスには、オリジナルのシーケンスがあればサイクルがあります。" - これはfalseです。 –
@ n.m .: Uh？リンクされたリストの場合、ループバックのプロパティは、 'x'個の項目ごとにステップオーバーすれば変更されません。どちらの場合も、両方の場合（サイクルがある）、または「n」または「n/x」のステップの後で停止する（サイクルがない）場合は、ステッピングを永遠に続けます。もちろん、元のサイクルの長さが 'k 'の場合、サイクル長は必ずしも' k/x'にはならないでしょう...しかしこれは引数とは無関係です。 – 6502
申し訳ありませんが、私は間違っていました。これは偽ではありません。私はこの声明を誤解した。 –