単方向linked listの循環参照判定をO(n)で行なう - やねうらおブログ(移転しました)「諸悪の根源は物理的」より。(id:ladybug:20051116経由) http://www.cotton-tree.com/garyu/archives/2005/11/post_156.html 単方向リンクリスト（連結リスト）がある。ノード数を n とするが、n の値は 分からない。リスト中にループ（循環参照）が存在するか否かを O(n) で判定する アルゴリズムを示せ。ただし、リストの各ノードの内容を変更してはならない。 つまり、単純にポインタが指したノード全てにマーキングをしておいて、 新しいノードに移るたびにマーキングされているかを調べることで判定することは 出来ない。 no markingが条件として与えられているが、当然、no labeling,no recursionで求めなければならない。labelingありなら、たとえば以下のように簡単に求まる。 bool isC
