Dies ist eine klassische von Microsoft geschriebene Testfrage. Die beiden Zeiger h1 und h2 durchlaufen die einfach verknüpfte Liste jedes Mal um einen Schritt, und h2 bewegt sich jedes Mal um zwei Schritte vorwärts Ring existiert nicht. Wenn h2 h1 berührt, das dahinter liegen sollte, bedeutet dies, dass eine Schleife vorhanden ist (d. h. eine Schleife auftritt).
Wenn der Ring nicht existiert, muss h2 zuerst auf NULL stoßen:
Wenn der Ring existiert, treffen sich h2 und h1 definitiv und der Treffpunkt liegt innerhalb des Rings: h2 durchläuft schneller als h1 und trifft sich definitiv nicht am Anfang der nicht mit dem Ring verknüpften Liste, wenn also sowohl h1 als auch h2 eintreten Der Ring Schließlich verringert jede Bewegung von h2 die Lücke zwischen h2 und h1 in Vorwärtsrichtung um 1. Schließlich wird die Lücke zwischen h1 und h2 auf 0 verringert, das heißt, sie treffen sich.
public static void main(String args[]){
SingleList list = new SingleList();
for(int i=0;i<100;i++){
list.add(i);
}
System.out.print(SingleList.isExistingLoop(list));
}
}
öffentlicher Knoten (Objektwert){
this.data = Wert;
}
publicNode(){
this.data = null;
this.next = null;
}
}
private void init(){
this.size = 0;
this.head = new Node();
}
öffentliche SingleList(){
init();
}
öffentlicher boolescher Wert enthält(Objektwert){
boolesches Flag = false;
Knoten p = head.next;
while(p!=null){
if(value.equals(p.data)){
Flag = wahr;
brechen;
}anders(
p = p.next;
)
}
Rückkehrflag;
}
public boolean add(Object value){
if(enthält(Wert))
return false;
anders{
Knoten p = neuer Knoten (Wert);
p.next=head.next;
head.next = p;
Größe++;
}
return true;
}
}