リンクリストのサイクルチェック

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

// labelingあり
bool isCyclic(list*p){
　set s;
　while(p!=null){
　　if (p in s) return true;
　　s.insert(p);
　　p = p->next;
　}
　return false;
}


// urao first
// ループの循環長をと想定しながら、nを2倍していく方法
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;
}

// 伝統的な方法
// 「片方を1つ進める間にもう片方を2進める」
// ループしてればいつかpがqに追いつくってことだね
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;
}