単方向linked listの循環参照判定をO(n)で行なう

program

「諸悪の根源は物理的」より。(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 isCyclic(list*p){

	set<list*> s;

	while(p!=null){

		if (p in s) return true;

		s.insert(p);

		p = p->next;

	}

	return false;

}


で、私が最初に思いついたのは、ループの循環長を2^{n}と想定しながら、nを2倍していく方法。これは、ノード数Nに対してworst caseでも3(N-1)回以内のループで済むことは保証されるからO(n)のアルゴリズムだ。(よね？このプログラムの解説は、id:ytqwerty:20051116#p1を参照のこと)



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;

}

しかし、伝統的な方法は、以下の通り。



# k.inaba 『『エキスパートCプログラミング』て本で全く同じ問題を見たことが

ありますが、そこでの正解はズバリ「片方を1つ進める間にもう片方を2進める」でした。』

※　これについて解説は「猪股健太郎の雑記」　http://blog.inomata.lolipop.jp/?eid=150020　が詳しい。


ソースコードで書くと、こんな感じだろうか。



bool isCyclic(list*p){

	list* q = p;

	while (p!=null) {

		q = q->next;

		p = p->next;

		if (p==null) break;

		p = p->next;

		if (p==q) return true;

	}

	return false;

}

※　qのnull checkは不要である。なぜなら、nullがあるのはlistの終端であり、qより歩幅のあるpが先に終端にたどり着くのは自明だからである。あと、評価順もこれがベストで、これよりシンプルにはならない。(はずだ。whileの条件式を (p!=null && p->next!=null)として、「p = p->next」以下の3行を「p = p->next->next;」としたほうが見かけは単純になるが、p->nextへのアクセスがwhileのところと2つに分断されるので、上のコードより劣ると思う)


私が考えついたほうのアルゴリズムは独特で、効率も上のと似たりよったりだから(むしろ、私のアルゴリズムのほうがメモリアクセスが少ないぶん、速い意味がある)、別段、負けた気はしないのだが、ただ、その本(asin:4756116396)を読んでいなかったことが悔しかっただけで..。