循環参照した短方向リンクリストを O(n) で検出する気持ちさえあれば

http://d.hatena.ne.jp/ladybug/20051116#p1
O(n^2)ならできそうなんだけどなぁ…。
そうか！走査を終えたノードを解放していけば、循環でアクセス違反が起きるので判別できるぞ！
…ごめんなさい。
マーキング無しということは、マーキング同様の手法も無しということらしいので、n個の配列とかも無し、スタックを同様に使うのも無し…ううむ。
つまるところ、個数nがわかっていれば、適当にあっちこっち巡回してn回以上リンクを辿っていればそれは循環とわかる、が、nがわからないので、nを求めるためにはやはりマーキングがいるよね、という話らしい。なのでこの手の手法は使えない。搭載メモリにスワップファイルのサイズを加えたページファイルの合計値をnの代わりに使うとかもだめでしょうし…。
例えばカーソルをふたつ用意して、片方を1つ進める間にもう片方を2進める。同じところからはじめて再び合流するようなことがあれば循環とか？

ついき
えーと、コメントされなきゃ私自身含めて誰もがテキトーこいただけとしか思わなかったような気がする、と無責任な本音を言いつつ、今更====してもコメント欄は隠せないので、開き直ってladybugさんのコメント欄のやねうらおさんの方法を考えてみます。
考え方としてはそれまで通過してきた数を元にnを仮定する、で、あるノードと、それまで通過してきたノードとの間で循環が起きてないことは、そのノードからn+1だけ辿って戻ってこなければOK。
そうやって順番に循環が起きてないエリアを広げていくとー、とー、走査数が1,1+2,1+2+3…と増えていくわけでこれって冒頭にオーダーだけ書いたO(n^2)と同じ？
いや違う。やねうらおさんのコードはむしろ先行する方が主体で、循環して無いことを確認できたエリアを表すカーソルは、遅れて飛び飛びについてきている。ビットシフトの意味がいまいちわからないですが、飛び飛びにエリアを広げて、途中に循環があった場合はどうなるかというと…その時には先行しているカーソルは倍以上先に進んでいる筈で、途中に循環があってもとっくに通り越して手元まで戻っている筈、と、そのためのビットシフト、と、成程…。