Ini adalah pertanyaan tes tertulis Microsoft klasik. Kedua penunjuk h1 dan h2 melintasi daftar tertaut tunggal dari awal. h1 bergerak maju 1 langkah setiap kali, dan h2 bergerak maju 2 langkah setiap kali ring tidak ada ; Jika h2 menyentuh h1 yang seharusnya berada di belakangnya, berarti ada loop (yaitu terjadi loop).
Jika ring tidak ada, h2 harus menemui NULL terlebih dahulu:
Jika ring ada, h2 dan h1 pasti akan bertemu, dan titik pertemuannya ada di dalam ring: h2 melintasi lebih cepat dari h1, dan pasti tidak akan bertemu di awal daftar tertaut non-ring, jadi ketika h1 dan h2 keduanya masuk ring Terakhir, setiap gerakan h2 akan mengurangi jarak antara h2 dan h1 ke arah depan sebesar 1. Terakhir, jarak antara h1 dan h2 akan berkurang menjadi 0, yaitu keduanya bertemu.
public static void main(String args[]){
Daftar Daftar Tunggal = Daftar Tunggal baru();
untuk(int i=0;i<100;i++){
daftar.tambahkan(i);
}
System.out.print(SingleList.isExistingLoop(daftar));
}
}
Node publik(Nilai objek){
this.data = nilai;
}
Node publik(){
ini.data = null;
ini.berikutnya = null;
}
}
kekosongan pribadi init(){
ini.ukuran = 0;
this.head = Node baru();
}
Daftar Tunggal publik(){
init();
}
boolean publik berisi(Nilai objek){
bendera boolean = false;
Node p = head.next;
sementara(p!=batal){
if(nilai.sama dengan(p.data)){
bendera = benar;
merusak;
}kalau tidak(
p = p.berikutnya;
)
}
bendera kembali;
}
penambahan boolean publik(Nilai objek){
jika(berisi(nilai))
kembali salah;
kalau tidak{
Node p = Node baru(nilai);
p.next=kepala.next;
kepala.berikutnya = p;
ukuran++;
}
kembali benar;
}
}