亀とうさぎの会議はループの存在を結論付けていると理解していますが、待ち合わせ場所でうさぎを維持しながら、リンクリストの先頭に亀を移動し、その後、一度に両方を1ステップずつ移動すると、開始点で会うようになります。サイクルの？
質問する
90487 次
23 に答える
372
ウィキペディアで提供されている循環検出アルゴリズムを明確にしようと思います-私自身の言葉でTortoise_and_hare。
使い方
上の図のように、リストの先頭をサイクルで指す亀とうさぎ（ポインターの名前）を用意しましょう。
亀を一度に1ステップ、ウサギを一度に2ステップ動かすと、最終的にはある時点で出会うと仮定しましょう。まず、この仮説が正しいことを示しましょう。
この図は、サイクルのあるリストを示しています。サイクルの長さはでnあり、最初mはサイクルから離れています。kまた、待ち合わせ場所がサイクルの始まりから少し離れており、亀とウサギがi合計の歩数を踏んだときに出会うとしましょう。（それまでに、Hareは2i総ステップを踏んでいたでしょう。）
次の2つの条件が満たされている必要があります。
1) i = m + p * n + k
2) 2i = m + q * n + k
最初のものは、カメがiステップを動かし、これらのiステップで、最初にサイクルに到達すると言います。p次に、正の数のサイクルタイムを通過しますp。最後に、kうさぎに出会うまで、より多くのノードを通過します。
うさぎについても同様のことが言えます。ステップを移動2iし、これらの2iステップで最初にサイクルに到達します。q次に、正の数のサイクルタイムを通過しますq。最後にk、亀に出会うまで、さらに多くのノードを通過します。
ノウサギはカメの2倍の速度で移動するため、両方が待ち合わせ場所に到達するまでの時間は一定です。
したがって、単純な速度、時間、距離の関係を使用することにより、
2 ( m + p * n + k ) = m + q * n + k
=> 2m + 2pn + 2k = m + nq + k
=> m + k = ( q - 2p ) n
、、、、、のうちm、最初の2つは指定されたリストのプロパティです。この方程式を真にする、、の値のセットが少なくとも1つあることを示すことができれば、仮説が正しいことを示します。nkpqkqp
そのようなソリューションセットの1つは次のとおりです。
p = 0
q = m
k = m n - m
これらの値が次のように機能することを確認できます。
m + k = ( q - 2p ) n
=> m + mn - m = ( m - 2*0) n
=> mn = mn
このセットの場合i、
i = m + p n + k
=> m + 0 * n + mn - m = mn
もちろん、これが必ずしもi可能な限り最小であるとは限らないことを確認する必要があります。言い換えれば、カメとウサギは以前に何度も会ったことがあるかもしれません。ただし、少なくとも一度はそれらが出会うことを示しているので、仮説は正しいと言えます。したがって、1つを1ステップずつ移動し、もう1つを一度に2ステップずつ移動すると、それらは会う必要があります。
これで、サイクルの開始を見つける方法であるアルゴリズムの2番目の部分に進むことができます。
サイクル開始
亀とウサギが出会ったら、亀をリストの最初に戻し、出会った場所（kサイクルの始まりから少し離れたところ）にウサギを置きましょう。
同じ速度（両方とも1ステップ）で移動させると、初めて会うのがサイクルの始まりになるという仮説が立てられています。
この仮説を証明しましょう。
まず、オラクルが何であるかを教えてくれると仮定しましょうm。
次に、彼らにm + k階段を移動させると、亀は最初に出会った場所に到着する必要があります（kサイクルの開始から一歩離れています-図を参照）。
以前、それを示しましたm + k = (q - 2p) n。
m + kステップはサイクルの長さの倍数であるためn、その間、うさぎはサイクル（）回を通過q-2pし、同じポイントに戻ります（kサイクルの開始からステップ離れます）。
さて、ステップを動かさずに、ステップm + kだけ動かせばm、亀はサイクルの始まりに到着します。うさぎは、（ ）ローテーションkを完了するには至らないステップです。q-2pサイクル開始の前にステップを開始したのでk、ウサギはサイクル開始に到達する必要があります。
m結果として、これは、彼らが初めていくつかのステップの後に始まるサイクルで会わなければならないことを説明します（カメはステップの後にサイクルに到着したばかりであり、すでに入っていたウサギを見ることができなかったため、非常に初めてですサイクル）。
これで、それらが出会うまで移動する必要のあるステップ数が、リストの先頭からサイクルの先頭までの距離であることがわかりましたm。もちろん、アルゴリズムは何mであるかを知る必要はありません。亀とうさぎの両方が出会うまで、一度に一歩ずつ移動します。ミーティングポイントはサイクル開始である必要があり、ステップ数はサイクル開始までの距離（m）である必要があります。リストの長さがわかっていると仮定すると、mリストの長さから減算するサイクルの長さを計算することもできます。
于 2011-05-24T12:56:28.027 に答える
142
この画像を参照してください：
ミーティング前にslowPointerが移動した距離=x+ y
ミーティング前にfastPointerが移動した距離=（x + y + z）+ y = x + 2y + z
fastPointerはslowPointerの2倍の速度で移動するため、ミーティングポイントに到達すると、両方の時間が一定になります。
したがって、単純な速度、時間、距離の関係を使用することにより、2（x + y）= x + 2y + z => x + 2y + z = 2x + 2y => x = z
したがって、slowPointerをリンクリストの先頭に移動し、slowPointerとfastPointerの両方を一度に1つのノードに移動させることにより、両方がカバーする距離が同じになります。
それらは、リンクリストでループが開始するポイントに到達します。
于 2015-08-24T19:50:02.920 に答える
93
これは、サイクル検出のためのフロイドのアルゴリズムです。アルゴリズムの第2フェーズについて質問しています。サイクルの一部であるノードを見つけたら、どのようにしてサイクルの開始を見つけるのでしょうか。
フロイドのアルゴリズムの最初の部分では、ウサギは亀のステップごとに2つのステップを移動します。カメとウサギが出会った場合、サイクルがあり、合流点はサイクルの一部ですが、必ずしもサイクルの最初のノードである必要はありません。
亀とうさぎが出会うと、X i = X 2iとなる最小のi（亀が踏んだ歩数）が見つかりました。X 0からサイクルの開始までのステップ数をmuで表し、サイクルの長さをlambdaで表します。次に、i = mu + a lambda、および2i = mu + b lambdaです。ここで、aとbは、カメとウサギがサイクルを何回周回したかを示す整数です。2番目の方程式から最初の方程式を引くとi=（ba）* lambdaになるため、iはラムダの整数倍になります。 したがって、X i + mu = Xmu。X iは、カメとウサギの合流点を表します。亀を開始ノードXに戻した場合0、そして亀と野ウサギを同じ速度で続行させます。muの追加ステップの後、亀はX muに到達し、ウサギはX i + mu = X muに到達するため、2番目の合流点はサイクル。
于 2010-05-29T19:37:57.903 に答える
82
オールドモンクのシンプルで賛成の少ない答えは、速いランナーが1つの完全なサイクルだけを完了したときにサイクルを見つけることを説明しています。この回答では、遅いランナーがループに入る前に、速いランナーがループを複数回実行した場合について説明します。
同じ画像を使用する：
高速ランナーが低速と高速の出会いの前にループをm回実行したとしましょう。この意味は：
- 低速走行距離：x + y
- 高速で走る距離：x + m（y + z）+ yすなわち、それらが出会う場所での余分なy
高速は低速の2倍の速度で実行され、同時に実行されているため、低速で実行される距離を2倍にすると、高速で実行される距離が得られることを意味します。したがって、
- 2（x + y）= x + m（y + z）+ y
xを解くと、
x =（m-1）（y + z）+ z
実際のシナリオでは、x = （m --1）完全なループ実行+余分な距離zを意味します。
したがって、一方のポインターをリストの先頭に置き、もう一方のポインターをミーティングポイントに置いたままにすると、同じ速度でそれらを移動すると、ループ内ポインターがループのm-1回の実行を完了し、もう一方のポインターに会うことになります。ループの先頭にあるポインタ。
于 2016-03-25T06:08:56.430 に答える
14
とても簡単です。あなたは相対速度の観点から考えることができます。ウサギが2つのノードを移動し、カメが1つのノードを移動する場合、カメに対して、ウサギは1つのノードを移動します（カメが静止していると仮定します）。したがって、循環リンクリスト内の1つのノードを移動すると、その時点で再び会うことになります。
循環リンクリスト内の接続点を見つけた後、問題は2つのリンクリスト問題の交点を見つけることになります。
于 2014-10-26T04:21:13.460 に答える
10
最初の衝突時に、亀は上記のようにm+kステップ移動しました。うさぎは亀の2倍の速さで動きます。つまり、うさぎは2（m + k）ステップ移動します。これらの単純な事実から、次のグラフを導き出すことができます。
この時点で、カメを最初に戻し、ウサギとカメの両方が一度に1ステップずつ移動する必要があることを宣言します。定義上、mステップ後、カメはサイクルの開始時になります。うさぎはどこにありますか？
うさぎもサイクルの始まりになります。これは2番目のグラフから明らかです。カメが最初に戻ったとき、ウサギは最後のサイクルにkステップ入っていました。m歩後、うさぎは別のサイクルを完了し、カメと衝突します。
于 2014-08-20T00:06:16.160 に答える
9
アプローチ：
2つのポインタがあります：
- 一度に1つのノードを移動する低速ポインター。
- 一度に2つのノードを移動する高速ポインター。
2つのポインターが一致する場合、ループがあることを証明します。それらが出会うと、ノードの1つがヘッドを指し、両方が一度に1つのノードを続行します。彼らはループの開始時に会います。
理論的根拠： 2人が円形のトラックを歩いているとき、一方はもう一方の2倍の速度で、どこで出会うのですか？まさに彼らが始めた場所。
ここで、高速ランナーがステップラップでkステップの先頭に立っているとします。n彼らはどこで会いますか？まさにn-kステップで。遅いランナーが(n-k)ステップをカバーしたとき、速いランナーはステップをカバーしたでしょうk+2(n-k)。（つまり、k+2n-2kステップ、つまり2n-kステップ）。つまり(n-k)、ステップ（パスは円形であり、それらが出会うまでのラウンド数は関係ありません。私たちは、それらが出会う位置にのみ関心があります）。
さて、そもそもファストランナーはどのようにしてステップの先頭に立っkたのでしょうか？遅いランナーがループの開始に到達するのに多くのステップを要したからです。したがって、ループの開始はヘッドノードからkステップです。
注：両方のポインターが出会ったノードはk、ループの開始からステップ離れており（ループ内）、ヘッドノードもkループの開始からステップ離れています。したがって、これらのノードのボットから1ステップの等ペースでポインターを進めると、ループの開始時にそれらが合流します。
簡単だと思います。あいまいな部分があれば教えてください。
于 2014-05-09T11:48:46.253 に答える
5
さて、うさぎと亀がサイクルの開始からkステップ離れた点で出会うと仮定しましょう。サイクルが開始するまでのステップ数はmuで、サイクルの長さはLです。
だから今、待ち合わせ場所で->
カメがカバーする距離=mu+ a * L+k-式1
（サイクルの開始に到達するために実行されるステップ+サイクルの「a」反復をカバーするために実行されるステップ+サイクルの開始からkステップ）（ここで、aは正の定数です）
うさぎがカバーする距離=mu+ b * L+k-式2
（サイクルの開始に到達するために実行されるステップ+サイクルの「b」反復をカバーするために実行されるステップ+サイクルの開始からkステップ）（ここで、bは正の定数であり、b> = a）
したがって、うさぎがカバーする余分な距離は次のようになります=式2-式1 =（ba）* L
うさぎは亀の2倍の速さで動くので、この距離も出発点から亀までの距離に等しいことに注意してください。これは、サイクルの複数のトラバーサルを含めない場合、最初からの待ち合わせポイントの距離でもある「mu+k」と同等と見なすことができます。
したがって、mu + k =（ba）* L
したがって、このポイントからのmuステップは、サイクルの開始に戻ります（サイクルの開始からkステップがすでにミーティングポイントに到達するために実行されているため）。これは、同じサイクルまたは後続のサイクルのいずれかで発生する可能性があります。したがって、亀をリンクリストの先頭に移動すると、サイクルの開始点に到達するまでにmuステップが必要になり、ウサギもサイクルの先頭に到達するためにmuステップを実行するため、両方がサイクルの開始点。
PS正直なところ、元のポスターと同じ質問が頭に浮かび、最初の答えを読んだところ、いくつかのことが明らかになりましたが、最終結果を明確に得ることができなかったので、自分のやり方でやってみました。理解しやすいと思いました。
于 2013-07-22T06:38:19.863 に答える
4
問題をループ問題に減らしてから、最初の問題に戻ります
次の説明の方が直感的だと思います。
頭（O）から始まる2つのポインター（1 =亀と2 =うさぎ）を取ります。1のステップ長は1、2のステップ長は2です。1がそのサイクルの開始ノード（A ）に到達した瞬間を考えてみてください。
次の質問に答えたいと思います。「1がAにあるとき2はどこにありますか？」。
したがって、
OA = aは自然数（a >= 0）です。しかし、それは次のように書くことができます：a = k*n + b、ここでa, k, n, b are natural numbers：n=サイクル長k >= 0=定数0 <= b <= n-1
それはそれを意味し
b = a % nます。例：if
a = 20andn = 8= >k = 2andbecauseb = 4。20 = 2*8 + 41でカバーされる距離は
d = OA = a = k*n + bです。しかし同時に、2つのカバーD = 2*d = d + d = OA + d = OA + k*n + b。これは、2がAにある場合、カバーする必要があることを意味しますk*n + b。ご覧のとおり、kはラップ数ですが、それらのラップの後、2はAからb遠くになります。したがって、1がAにあるときに2がどこにあるかを見つけました。そのポイントをここで、と呼びましょう。BAB = b
ここで、問題を円に減らします。質問は「待ち合わせ場所はどこですか？」です。。そのCはどこにありますか？
すべてのステップで、2は（たとえばメートル）で1から距離を縮めます。これは、1が2で2から遠ざかっているためですが、同時に2は1で1に近づきます。
112したがって、交点は1と2の間の距離がゼロになるときです。これは、2
n - bが距離を縮めることを意味します。これを達成するために、1がn - bステップを実行し、2が2*(n - b)ステップを実行します。したがって、交点はA
n - b（時計回り）から遠くなります。これは、 2と出会うまで1でカバーされる距離だからです。=> CとAの間の距離は、とです。距離は数学的距離ではないため、AとCの間のステップ数であるとは思わないでください（Aは始点、Cは終点）。CA = bAC = AB + BC = n - bCA = n - ACAC = CAACそれでは、最初のスキーマに戻りましょう。
私たちはそれを知っています
a = k*n + bそしてCA = b。2つの新しいポインタ1'と1''をとることができます。ここで、1'は頭（O）から始まり、1''は交点（C）から始まります。
1'がOからAに移動する間、1''はCからA
kに移動し、ラップを終了し続けます。したがって、交点はAです。
于 2015-10-15T09:40:21.107 に答える
4
高校で教えられている相対速度の概念を使用した簡単な説明-物理学101/運動学の講義。
リンクリストの開始から円の開始までの距離が
xホップであると仮定しましょう。円の始点を点と呼びましょうX（大文字で-上の図を参照）。また、円の合計サイズがNホップであると仮定します。うさぎの速度=2*亀の速度。つまり
1 hops/sec、2 hops/secそれぞれと亀が円の始点に達したとき、うさぎは図のポイントでさらにホップする
X必要があります。（うさぎは亀の2倍の距離を移動したため）。xYしたがって、残りの円弧の長さはXからYまで時計回りになります
N-x。これはまた、ノウサギとカメが出会うことができるようにするための、ウサギとカメの間の相対的な距離でもあります。この相対的な距離が時間内にカバーされるとしましょうt_m。つまり、会う時間です。相対速度は(2 hops/sec - 1 hops/sec)すなわち1 hops/secです。したがって、相対距離=相対速度X時間を使用すると、t=N-x秒になります。N-xですから、亀とうさぎの両方の待ち合わせ場所にたどり着くのに時間がかかります。今
N-x秒の時間と1 hops/sec速度で、ポイントで以前にいたカメはX、ミーティングポイントに到達するためのNxホップをカバーしMます。つまり、ミーティングポイントMが=N-xから反時計回りにホップしていることを意味しますX（これはさらに意味します）=>ポイントから時計回りxまでの距離が残っていることを意味します。MXただし、リンクリストの先頭から
xポイントに到達するまでの距離でもあります。Xここで、ホップ数が何に
x対応するかは関係ありません。LinkedListの先頭に1匹のカメを置き、待ち合わせ場所に1匹の亀を置いて、飛び跳ねたり歩いたりすると、必要なポイント（またはノード）であるMポイントで待ち合わせます。X
于 2017-05-25T05:17:23.147 に答える
3
-ループの前にkステップがあります。kが何であるかわからないので、調べる必要はありません。kだけで抽象的に作業できます。
--kステップ後
-----Tはサイクル開始時です
----- Hはサイクルにkステップです（彼は合計2kになり、したがってkはループになります）
**ループサイズになりました-k離れています
（k == K == mod（loopsize、k）-たとえば、ノードが5ノードサイクルの2ステップである場合、7、12、または392ステップであるため、サイクルの大きさはkではありません。要因で。
一方が他方の2倍の速さで動いているため、単位時間あたり1ステップの速度で互いに追いつくため、ループサイズ--kで合流します。
これは、サイクルの開始に到達するのにkノードかかることを意味します。したがって、ヘッドからサイクルスタートまでの距離と衝突からサイクルスタートまでの距離は同じです。
したがって、最初の衝突の後、Tを頭に戻します。TとHは、それぞれ1の速度で移動すると、サイクルスタート時に合流します。（両方ともkステップ）
これは、アルゴリズムが次のことを意味します。
- 頭からT=t.nextとH.next.nextが衝突するまで移動します（T == H）（サイクルがあります）
//ループの長さを計算することにより、k=0またはTとHがループの先頭で出会った場合のケースに対処します
-カウンターでTまたはHを動かして、サイクルの長さを数えます
-ポインタT2をリストの先頭に移動します
--サイクルステップのポインタ長を移動します
-別のポインタH2をヘッドに移動します
-サイクルの開始時に出会うまで、T2とH2をタンデムに移動します
それでおしまい！
于 2017-03-05T23:36:26.760 に答える
3
図に示すように、ポインターが点Pで出会った場合、距離Z + Yは点Pであり、X + Yも点Pであり、これはZ=Xを意味します。そのため、あるポインターをPから移動し、別のポインターをstart（S）からそれらが出会うまで移動し続けます。つまり、同じポイントM（Pからの距離ZとSからのX）に等しい距離（ZまたはX）を移動します。ループの開始。単純！
于 2018-07-17T06:21:37.430 に答える
3
呼び出し距離は、ポインターがたどるリンクの数であり、アルゴリズムが低速ポインターを1リンク、高速ポインターを2リンク移動するのにかかる反復回数です。長さCのサイクルの前にN個のノードがあり、サイクルオフセットk=0からC-1でラベル付けされています。
サイクルの開始に到達するには、slowにはN時間と距離がかかります。これは、サイクル内で高速がNの距離を取ることを意味します（そこに到達するためにN、スピンするためにN）。したがって、時間Nでは、低速はサイクルオフセットk = 0にあり、高速はサイクルオフセットk = NmodCにあります。
N mod Cがゼロの場合、低速と高速が一致し、サイクルは時間Nおよびサイクル位置k=0で検出されます。
N mod Cがゼロでない場合、fastはslowに追いつく必要があります。これは、時間NがサイクルのC-（N mod C）距離遅れている場合です。
高速は低速の1ごとに2を移動し、反復ごとに距離を1ずつ減らすため、これには、時間Nでの高速と低速の間の距離（C-（N mod C））と同じくらいの追加時間がかかります。スローはオフセット0から移動しているため、これはそれらが出会うオフセットでもあります。
したがって、N mod Cがゼロの場合、フェーズ1は、サイクルの開始時にN回の反復後に停止します。それ以外の場合、フェーズ1は、サイクルへのオフセットC-（N mod C）でのN + C-（N mod C）の反復後に停止します。
// C++ pseudocode, end() is one after last element.
int t = 0;
T *fast = begin();
T *slow = begin();
if (fast == end()) return [N=0,C=0];
for (;;) {
t += 1;
fast = next(fast);
if (fast == end()) return [N=(2*t-1),C=0];
fast = next(fast);
if (fast == end()) return [N=(2*t),C=0];
slow = next(slow);
if (*fast == *slow) break;
}
さて、フェーズ2：slowはサイクルに到達するためにさらにNステップかかります。その時点で、fast（現在はタイムステップごとに1つ移動）は（C-（N mod C）+ N）mod C=0になります。フェーズ2の後のサイクルの開始時。
int N = 0;
slow = begin();
for (;;) {
if (*fast == *slow) break;
fast = next(fast);
slow = next(slow);
N += 1;
}
完全を期すために、フェーズ3は、サイクルをもう一度移動してサイクル長を計算します。
int C = 0;
for (;;) {
fast = next(fast);
C += 1;
if (fast == slow) break;
}
于 2018-12-06T07:02:26.167 に答える
3
これにはすでにたくさんの答えがありますが、私はかつて私にとってより視覚的に直感的なこの図を思いつきました。おそらくそれは他の人々を助けることができます。
私にとっての主なaha-momentsは次のとおりです。
T（カメ）をT1（プレループ）とT2 （インループ）に分割します。
視覚的に重なるHからTを引きます。残っているもの（H --T = H' ）はTに等しい。
- 残りの計算は非常に簡単です。
于 2019-03-18T18:15:38.287 に答える
2
上記のすべての分析で、あなたが例によって学ぶ人であるならば、私は他の誰もが説明しようとした数学を説明するのに役立つ短い分析と例を書こうとしました。どうぞ！
分析：
2つのポインターがあり、一方が他方よりも速く、それらを一緒に移動すると、最終的にはそれらが再び出会ってサイクルを示すか、ヌルがサイクルがないことを示します。
サイクルの開始点を見つけるために、...
m頭からサイクルの開始までの距離です。dサイクル内のノードの数です。p1遅いポインタの速度になります。p2より速いポインタの速度である、例えば。2は、一度に2つのノードをステップスルーすることを意味します。次の反復を観察します。
m = 0, d = 10: p1 = 1: 0 1 2 3 4 5 6 7 8 9 10 // 0 would the start of the cycle p2 = 2: 0 2 4 6 8 10 12 14 16 18 20 m = 1, d = 10: p1 = 1: -1 0 1 2 3 4 5 6 7 8 9 p2 = 2: -1 1 3 5 7 9 11 13 15 17 19 m = 2, d = 10: p1 = 1: -2 -1 0 1 2 3 4 5 6 7 8 p2 = 2: -2 0 2 4 6 8 10 12 14 16 18
m上記のサンプルデータから、速いポインターと遅いポインターが出会うたびに、それらがサイクルの開始から一歩離れていることが簡単にわかります。これを解決するには、速いポインターを先頭に戻し、その速度を遅いポインターの速度に設定します。それらが再び出会うとき、ノードはサイクルの始まりです。
于 2014-11-14T01:14:49.270 に答える
1
彼らが出会うとき、それが出発点であるというのは本当ではないと思います。しかし、はい、他のポインター（F）が前のミーティングポイントにあった場合、そのポインターはループの開始ではなくループの終了になり、ポインター（S）はリストの最初から開始します。ループの開始時に終了します。例：
1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->8
Meet at :16
Start at :8
public Node meetNodeInLoop(){
Node fast=head;
Node slow=head;
fast=fast.next.next;
slow=slow.next;
while(fast!=slow){
fast=fast.next;
fast=fast.next;
if(fast==slow) break;
slow=slow.next;
}
return fast;
}
public Node startOfLoop(Node meet){
Node slow=head;
Node fast=meet;
while(slow!=fast){
fast=fast.next;
if(slow==fast.next) break;
slow=slow.next;
}
return slow;
}
于 2013-10-06T14:21:16.690 に答える
1
まあ言ってみれば、
N[0] is the node of start of the loop,
m is the number of steps from beginning to N[0].
2つのポインターAとBがあり、Aは1倍速で実行され、Bは2倍速で実行され、どちらも最初から始まります。
AがN[0]に達すると、BはすでにN[m]にあるはずです。（注：Aはmステップを使用してN [0]に到達し、Bはmステップ先にある必要があります）
次に、AはBに衝突するためにさらにkステップを実行します。つまり、AはN [k]にあり、BはN [m + 2k]にあります（注：BはN [m]から始まる2kステップで実行する必要があります）
それぞれN[k]とN[m+ 2k]で衝突B、つまりk = m + 2k、つまりk = -m
したがって、N[k]からN[0]に戻るには、さらにmステップが必要です。
簡単に言うと、衝突ノードを見つけた後、さらにmステップ実行する必要があります。最初から実行するポインターと衝突ノードから実行するポインターを持つことができます。これらはmステップ後にN[0]で合流します。
したがって、擬似コードは次のようになります。
1) A increase 1 step per loop
2) B increase 2 steps per loop
3) if A & B are the same node, cycle found, then go to 5
4) repeat from 1
5) A reset to head
6) A increase 1 step per loop
7) B increase 1 step per loop
8) if A & B are the same node, start of the cycle found
9) repeat from 6
于 2015-12-15T07:40:34.983 に答える
1
これを図で操作すると役立ちます。私は方程式なしで問題を説明しようとしています。
- うさぎと亀を輪になって走らせ、うさぎを2回走らせると、1周の終わりにうさぎの亀は半分になります。ウサギのカメからの2周の終わりに、1周を行ったはずであり、それらは両方とも会います。これは、うさぎが3回走る場合のように、すべての速度に適用されます。うさぎの1周は亀の1/3に等しいので、うさぎの亀の3周の終わりには、1周をカバーします。
- ここで、ループのmステップ前にそれらを開始すると、ループの前でより速いウサギが開始されていることを意味します。したがって、亀がループの開始点に到達した場合、うさぎはループのmステップ先にあり、それらが出会ったとき、ループ開始のmステップ前になります。
于 2017-09-03T07:04:45.597 に答える
0
これを数学的に説明している答えのほとんどは、「カメを待ち合わせ場所に置いたままリンクリストの先頭に移動し、その後、両方を一度に1ステップずつ移動すると、サイクルの開始点でどのように出会うのですか？」
次の方法も、舞台裏でのフロイドサイクル検出と同じように機能しますが、理論的根拠は単純ですが、O（n）メモリが犠牲になります。
サイクルの始まりを見つけるためのより簡単なアプローチ/合理性を追加したいと思います。この方法はどこにも言及されていなかったので、私はここでこれをテストしました：https ://leetcode.com/problems/linked-list-cycle-ii/そしてそれはすべてのテストケースに合格しました。
LinkedListのヘッドリファレンスが与えられたとしましょう。
public ListNode detectCycle(ListNode head) {
// Consider a fast pointer which hops two nodes at once.
// Consider a slow pointer which hops one node at once.
// If the linked list contains a cycle,
// these two pointers would meet at some point when they are looping around the list.
// Caution: This point of intersection need not be the beginning of the cycle.
ListNode fast = null;
ListNode slow = null;
if (head != null) {
if (head.next != null) {
fast = head.next.next;
slow = head;
} else {
return null;
}
}
while (fast != null && fast.next != null) {
// Why do we need collection here? Explained below
Set<ListNode> collection = new HashSet<>();
if (fast == slow) {
// Once the cycle is detected,
we are sure that there is beginning to the cycle.
// In order to find this beginning,
// 1. move slow pointer to head and keep fast pointer at
the meeting point.
// 2. now while moving slow and fast pointers through a
single hop, store the slow reference in a collection.
// 3. Every time you hop the fast pointer, check the fast
pointer reference exits in that collection.
// Rationale: After we moved slow pointer to the head,
we know that slow pointer is coming behind the fast
pointer, since collection is storing all nodes from the
start using slow pointer, there is only one case we get
that fast pointer exists in the collection when slow
pointer started storing the nodes which are part of the
cycle. Because slow pointer can never go ahead of fast
pointer since fast pointer already has an head-start, at
the same time, the first occurence will always be of the
starting point of the cycle because slow pointer can't
go ahead of fast pointer to store other nodes in the
cycle. So, the moment we first find fast pointer in that
collection means, that is the starting point of the
cycle.
slow = head;
collection.add(slow);
while (!collection.contains(fast)) {
slow = slow.next;
collection.add(slow);
fast = fast.next;
}
return fast;
}
fast = fast.next.next;
slow = slow.next;
}
return null;
}
于 2021-05-14T06:39:28.560 に答える
0
すべての答えを読むのに2時間費やした後、私はleetcodeでこのコメントを見つけました。言うまでもなく、それは私の夜を救った。
于 2021-09-19T05:54:35.007 に答える
-1
私はこの問題に対してすでに受け入れられた答えがあることを知っていますが、それでも私は流動的な方法で答えようとします。推定 ：
The length of the Path is 'X+B' where 'B' is the length of the looped path and X of the non looped path.
Speed of tortoise : v
Speed of hare : 2*v
Point where both meet is at a distance 'x + b - k' from the starting point.
さて、最初から時間「t」の後にウサギとカメを会わせましょう。
観察：
の場合、亀が移動した距離= v * t = x +（bk）（say）
次に、うさぎが移動した距離= 2 * v * t = x +（b --k）+ b（うさぎはすでにループ部分を通過しているため）
さて、会議の時間は同じです。
=> x + 2 * b-k = 2 *（x + b-k）
=> x = k
もちろん、これは、ループされていないパスの長さが、両方が出会うポイントからループの開始ポイントまでの距離と同じであることを意味します。
于 2011-09-21T15:39:38.610 に答える
-1
待ち合わせ場所の背後にある数学を考慮すると、実際には、両方が出発点で出会うことを証明するのは簡単です。
まず、mがリンクリスト内のサイクルの開始点を示し、 nがサイクルの長さを示すとします。次に、ウサギとカメが出会うために、私たちは持っています：
( 2*t - m )%n = (t - m) %n, where t = time (at t = 0 , both are at the start)
これをより数学的に述べる：
(2*t - m - (t - m) ) = 0 modulo n , which implies , t = 0 modulo n
したがって、それらは時間tで出会うことになります。これは、サイクルの長さの倍数である必要があります。これは、彼らがである場所で会うことを意味し
(t-m) modulo n = (0-m) modulo n = (-m) modulo nます。
さて、質問に戻ります。リンクリストの先頭から1つのポインタを移動し、交点から別のポインタを移動すると、mステップ後に、うさぎ（サイクル内を移動している）が次のポイントに到達します。これはサイクルの開始点に他なりません。したがって、mステップ後、サイクルの開始に到達 し、リンクリストの開始からm((-m) + m) modulo n = 0 modulo nステップを通過するときに、亀がそこで出会うことがわかります。
補足として、次の方法でそれらの交差の時間を計算することもできます。条件t = 0 modulo nは、それらがサイクル長の倍数である時間に会うことを示し、また、tはmよりも大きくなければなりません。サイクル。したがって、かかる時間は、 mより大きいnの最初の倍数に等しくなります。
于 2013-08-25T19:40:45.887 に答える
-1
ポインタが点yとzの交点で交わると仮定します。
nとmは、それぞれ、会議の前にポインターが取るループの数です。
残りの証明については、画像を参照してください。 リンクリストでループの開始点を見つけます
于 2019-09-08T09:47:13.173 に答える