ウサギとカメ - soutaroブログ

例えばカーソルをふたつ用意して、片方を1つ進める間にもう片方を2進める。同じところからはじめて再び合流するようなことがあれば循環とか？

ウサギとカメのアルゴリズム、とか言うらしいです。

必要なメモリは定数になりますが、計算量はどう考えてもO(n)にはならないので、別の話ですけど。

※追記

あれ？…これが答えなの？*1O(n)になる…かな？

※追記

なる！！！
リストが循環していないときは自明。n/2ステップ進めれば、ウサギが終端にたどり着く。

リストが循環しているとき、ウサギとカメの差をnとすれば、1ステップごとにウサギとカメの差は1ずつ縮まるので、nステップ進めれば同じノードを指すことになる→nで停止する。

すげーーー知らんかった…

そしてなによりショックだったのは、私がエキスパートCプログラミングを持ってること…読んでねーなあ…

*1:昼間、問題見たときにちょろっと書いとけばよかった