循環参照した短方向リンクリストを O(n) で検出する

http://www.cotton-tree.com/garyu/archives/2005/11/post_156.html 発見しただけ。
明日おぼえてたら考えよう。@IT とコメントにちょっと書き込みがある。*1私が応えることじゃないがコメントの、

１パスの処理で出来るのですか？

というのは、@IT のほうの

計算量も O(2n) になるような･･･。（くわしくないのでどなたかつっこんで下さい）

あたりからきてるんだろうか？
２パスで処理する場合、o(2n) になる、３パスなら o(3n) だ。o(n) も o(2n) も o(3n) も、すべて O(n) である。よって、問題文が誤記述ではないかぎり１パスで解くという制約はないはず。ただし、問題は

ノード数を n とするが、n の値は分からない。リスト中にループ（循環参照）が存在するか否か

であるため、１パス目が完了した時点で、それは循環参照はないということの証明であるため、２パス目を実行する必要性は絶対にないと思う。もうすこし突っ込んで言うと、

1度目でｎを求める。
2度目ででっち６号様のとおり

というアルゴリズムに対して循環参照をしているリストを投げると、１パス目で n を求めようとして無限ループして終わる、ということだ。

*1:この時点では返信３ぐらい