諸悪の根源は物理的

自分で解答を書こうと思っていたが、既に猪俣健太郎さんによる「アルゴリズムパズル（リンクリスト）に答える」に自分が予定していたより丁寧で分かりやすいものがある。これが、夕食を食べながら僕らがたどり着いた解答だった（出張中、皆で夕食を食べている時に出された問題だったのだ）。メイン部分を引用すると、

ポインタaとbを用意して、aは1ずつ、bは2ずつインクリメントする(次の要素に進む)。
もしループしているなら、aがループによって以前の要素に戻ってくる前に必ずbと同じ位置を指すときが来る。
ループしてなければbが終端に到達して終わり。

更に図を使った説明もあるので、興味のある方はリンク先を参照ください。

そして、やねうらおさんの「単方向linked listの循環参照判定をO(n)で行なう」には別解が示されている。これは思いつかなかったなあ。

bool isCyclic(list*p){
    int n=1,m=n;
    list*q=null;
    while(p!=null) {
        if(p==q) return true;
        if(--m ==0) { q=p; n<<=1; m=n; }
        p = p->next;
    }
    return false;
}

ポインタを2つ(p, q)用意する。qを固定して、pを1つづつ、一定長分だけ動かす。その途中でpがqと同じところを指せば循環参照検出。pが終端に達すれば循環参照無し。
その一定長でどちらの結論も出ない場合、qをpの現在位置に持ってきて（←ここが頭いいなあ）、「一定長」を更に長くして同じことを繰り返す。この擬似コードでは、一定長の増やし方は2のn乗でやっているが（n<<1 の部分）、効率を気にしなければ増やし方はどんな方法でも良いはずだ。
ytqwertyさんの「循環参照した短方向リンクリストを O(n) で検出する」にもこのコードについての説明がある。笑える解答と一緒に。

どちらの解も、ポインタの動きをアニメーションで表現すれば分かりやすくなる。やねさんの解答の方が見た目は面白い動きをするだろう。ああ、どうでもいい話だ。
さらにどうでもいい話として、猪俣さんの解答の方が優れている部分は、夕食の場で口だけで説明するのが簡単だということ。やねさんの解答をあの場で思いついても「解けた」ことにはならなかったかもしれない。説明が大変だからなあ。

最後に、無粋ながら、やねさんの記事中で気になったことが1つ。

私が考えついたほうのアルゴリズムは独特で、効率も上のと似たりよったりだから(むしろ、私のアルゴリズムのほうがメモリアクセスが少ないぶん、速い意味がある)

確かにやねさんのアルゴリズムのほうがメモリアクセスが少ない。しかし、ノードの数をnとした場合、比較の回数は最悪のケースで2n回となる。それに比べて、猪俣さんのアルゴリズムではn回で済む。細かい話だが、他人の引用以外に言うことがほとんど残っていないので、1つぐらい何か言っておきたかったのだ。以上！