Alternative 笑門来福 - この問題あなたは解けますか？

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

こーいうの大好きｗ
きゃっきゃ言いながら考えちゃう(言わないけど)ｗ

「n の値は分からない」ってのと「ただし、単純に～～」って条件がキツい＾＾

で、答えが分からないｗｗｗ

「マーキングによるループ検出が禁じ手」って部分がよく分からないってのもある。「単純なマーキングによるアルゴリズムは面白くないから却下」なのか、それともマーキングに類するもの全てが禁じ手なのか。後者だといよいよO(N)の解法の想像がつかないから、多分というか、きっと前者の筈だが。んーー。。。

でも考えてみることが大事だな＾＾


色々考えたけどギブアップｗ
で、このログエントリーにコメントされてたサイトを見て納得。

作業日誌（みすみロボット研究所） - アルゴリズム問題、解けるかな？

『逆方向への単方向リストに変換したときに、変換前のHead が指し示す要素のNextの値がNULLではない場合、循環参照がある』

なるほどー＾＾

これが正解かどうかは分からないけど、実際に図を書いて手順を追ってみて納得はできた。
自分もまだまだ頭が固いな＾＾；