これは、Microsoft の古典的な筆記試験の問題です。h1 と h2 は、単一リンクされたリストを最初からたどります。h1 は毎回 1 ステップ進み、h2 が NULL に遭遇すると、それは 2 ステップ進みます。リングが存在しない ; h2 がその後ろにあるはずの h1 に触れている場合、それはループが存在する (つまり、ループが発生している) ことを意味します。
リングが存在しない場合、h2 は最初に NULL に遭遇する必要があります。
リングが存在する場合、h2 と h1 は確実に出会い、出会い点はリング内にあります。h2 は h1 よりも速く移動し、非リングのリンク リストの先頭では間違いなく出会いません。そのため、h1 と h2 の両方が入ったとき、最後に、h2 が移動するたびに、h2 と h1 の間のギャップが前方向に 1 ずつ減少します。最終的に、h1 と h2 の間のギャップは 0 に減少します。つまり、h1 と h2 は一致します。
public static void main(String args[]){
SingleList リスト = new SingleList();
for(int i=0;i<100;i++){
list.add(i);
}
System.out.print(SingleList.isExistingLoop(リスト));
}
}
public Node(オブジェクト値){
this.data = 値;
}
publicNode(){
this.data = null;
this.next = null;
}
}
プライベート void init(){
this.size = 0;
this.head = 新しいノード();
}
public SingleList(){
init();
}
public boolean contains(オブジェクト値){
ブール値フラグ = false;
ノード p = head.next;
while(p!=null){
if(value.equals(p.data)){
フラグ = true;
壊す;
}それ以外（
p = p.next;
)
}
リターンフラグ;
}
public boolean add(オブジェクト値){
if((値)を含む)
false を返します。
それ以外{
ノード p = 新しいノード(値);
p.next=head.next;
head.next = p;
サイズ++;
}
true を返します。
}
}