Il s'agit d'une question de test écrite classique de Microsoft. Les deux pointeurs h1 et h2 parcourent la liste à chaînage unique depuis le début. h1 avance d'un pas à chaque fois, et h2 avance de 2 pas à chaque fois. l'anneau n'existe pas ; Si h2 touche h1 qui devrait être derrière lui, cela signifie qu'une boucle existe (c'est-à-dire qu'une boucle se produit).
Si l'anneau n'existe pas, h2 doit d'abord rencontrer NULL :
Si l'anneau existe, h2 et h1 se rencontreront certainement, et le point de rencontre est à l'intérieur de l'anneau : h2 traverse plus vite que h1 et ne se rencontrera certainement pas au début de la liste chaînée sans anneau, donc quand h1 et h2 entrent tous les deux l'anneau Enfin, chaque mouvement de h2 réduira de 1 l'écart entre h2 et h1 vers l'avant. Enfin, l'écart entre h1 et h2 sera réduit à 0, c'est-à-dire qu'ils se rencontrent.
public static void main(String args[]){
Liste SingleList = new SingleList();
pour(int i=0;i<100;i++){
list.add(i);
}
System.out.print(SingleList.isExistingLoop(liste));
}
}
Nœud public (valeur de l'objet) {
this.data = valeur ;
}
publicNode(){
this.data = null ;
this.next = null ;
}
}
init vide privé(){
this.size = 0;
this.head = nouveau nœud ();
}
liste unique publique(){
init();
}
public boolean contient (valeur de l'objet) {
indicateur booléen = faux ;
Nœud p = head.next ;
pendant que(p!=null){
if(value.equals(p.data)){
drapeau = vrai ;
casser;
}autre(
p = p.suivant ;
)
}
drapeau de retour ;
}
ajout booléen public (valeur de l'objet) {
si (contient (valeur))
renvoie faux ;
autre{
Nœud p = nouveau nœud (valeur);
p.next=head.next;
head.next = p;
taille++ ;
}
renvoie vrai ;
}
}