この問題あなたは解けますか？

　うちの社内ブログでちょっと盛り上がった頭の体操。頭の体操といっても多胡先生的な「とんち」ではなく、きちんとしたアルゴリズムの問題です。さて、あなたは解けますか？

【問題】 単方向リストがある。ノード数を n とするが、n の値は分からない。リスト中にループ（循環参照）が存在するか否かを O(n) で判定するアルゴリズムを示せ。ただし、単純にポインタが指したノード全てにマーキングをしておいて、新しいノードに移るたびにマーキングされているかを調べることで判定することは禁じ手とする。

　エンジニアを自認している人は是非チャレンジしてみてください。

　エンジニアでない人も下記を読めば問題の意味が理解できると思います。週末の頭の体操にどうぞ。

単方向リストって何？⇒クリック

O(n)って何？⇒クリック