[解決済み] サイクルリンクリストのサイクル開始ノードを見つけるにはどうしたらいいのでしょうか？

質問

カメとウサギが出会うことでループが成立することはわかったが、カメをリンクリストの先頭に移動させ、ウサギを出会いの場にとどめ、その後両者を1歩ずつ移動させると、どのようにしてサイクルの始点で出会うことができるのだろうか？

解決方法は？

これは Floydの周期検出アルゴリズム . このアルゴリズムの第2段階について質問しているのですが、サイクルの一部であるノードを見つけた後、どのようにして 開始 ということでしょうか？

フロイドのアルゴリズムの最初の部分では、ウサギはカメの1歩につき2歩移動します。 もし亀とウサギが出会うことがあれば、サイクルが存在し、会合点はサイクルの一部であるが、必ずしもサイクルの最初のノードとは限らない。

亀とうさぎが出会ったとき、Xを満たす最小のi（亀が歩いた数）を求めました。 <サブ i = X <サブ 2i . を得るためのステップ数をmuとすると、X <サブ 0 からサイクルの開始点までを表し、サイクルの長さをλとする。 すると、i = mu + a ラムダ、2i = mu + b ここで、aとbは亀とうさぎが何周したかを表す整数である。引き算をすると となり、i は整数の倍数である。 のラムダを使用する。 したがって、X <サブ i + mu = X <サブ μ . X <サブ i は、亀とウサギの会合点を表しています。 亀を出発点のノード X <サブ 0 そして、亀とウサギを同じ速度で走らせると、さらにmu歩で亀はXに到達します。 _μ に到達し、ウサギはX <サブ i + mu = X <サブ μ ということで、2つ目の会合点はサイクルの開始を意味する。