アルゴリズムパズル（リンクリスト）に答える

「諸悪の根源は物理的」より：

単方向リンクリスト（連結リスト）がある。ノード数を n とするが、n の値は分からない。リスト中にループ（循環参照）が存在するか否かを O(n) で判定するアルゴリズムを示せ。ただし、リストの各ノードの内容を変更してはならない。つまり、単純にポインタが指したノード全てにマーキングをしておいて、新しいノードに移るたびにマーキングされているかを調べることで判定することは出来ない。

これは有名なアルゴリズムなので知っている人も多いと思う。

回答

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

なぜこうなるのかは、図で説明するとわかりやすい。
循環のあるリンクリストを図に描くと、6の字、あるいはトランプゲームの「ブタのシッポ」のような形になる。円の部分が循環、ブタのシッポのように延びている先端がリンクの先頭だ。
今、ポインタを2つリンクの先頭にセットする。説明のため赤ポインタと青ポインタとしよう。そして、1ステップの間に、赤ポインタは1つずつ、青ポインタは2つずつ先に進めてみる。
そのようにして、赤ポインタが循環に差し掛かったところが下の図だ。プログラム的には循環の開始点を判別できないが、かならずこの瞬間は来る。その際、青ポインタはリンクの先を進んでいるのだが、この循環のどこかに存在していることは確実だ。
さてここで、さらに1ステップ進めるとどうなるか。もちろん赤ポインタは1進み、青ポインタは2進む。赤ポインタから見れば青との距離がさらに1大きくなる。ここで忘れていはいけないのが、赤ポインタも青ポインタも循環の上にいるということ。なので、赤ポインタが周回遅れしているという見方もできる。この見方に従えば、赤ポインタの後ろから青ポインタが1近づいたことになる。ずっとステップを進めれば、いつかは赤ポインタは青ポインタに追いつかれてしまうだろう。
さて、赤ポインタが循環に差し掛かったときに青ポインタがどこにいたとしても、2者の距離は円周の要素数よりも必ず小さいのだから、赤ポインタが一周するよりも、青ポインタに追いつかれるほうが早いことが証明できる。