Esta es una pregunta de prueba escrita de Microsoft clásica. Los dos punteros h1 y h2 atraviesan la lista enlazada individualmente desde el principio. h1 avanza 1 paso cada vez y h2 avanza 2 pasos cada vez. el anillo no existe; si h2 toca h1 que debería estar detrás de él, significa que existe un bucle (es decir, se produce un bucle).
Si el anillo no existe, h2 debe encontrar NULL primero:
Si el anillo existe, h2 y h1 definitivamente se encontrarán, y el punto de encuentro está dentro del anillo: h2 atraviesa más rápido que h1 y definitivamente no se encontrará al comienzo de la lista vinculada sin anillo, por lo que cuando h1 y h2 entren el anillo Finalmente, cada movimiento de h2 reducirá la brecha entre h2 y h1 en la dirección de avance en 1. Finalmente, la brecha entre h1 y h2 se reducirá a 0, es decir, se encuentran.
principal vacío estático público (String args []) {
Lista SingleList = nueva SingleList();
para(int i=0;i<100;i++){
lista.add(i);
}
System.out.print(SingleList.isExistingLoop(lista));
}
}
Nodo público (valor del objeto) {
this.data = valor;
}
nodo público(){
this.data = nulo;
this.siguiente = nulo;
}
}
inicio vacío privado(){
este.tamaño = 0;
this.head = nuevo Nodo();
}
Lista única pública(){
inicio();
}
booleano público contiene (valor del objeto) {
bandera booleana = falso;
Nodo p = head.next;
mientras(p!=nulo){
if(valor.equals(p.datos)){
bandera = verdadero;
romper;
}demás(
p = p.siguiente;
)
}
bandera de retorno;
}
agregar booleano público (valor del objeto) {
si (contiene (valor))
devolver falso;
demás{
Nodo p = nuevo Nodo(valor);
p.siguiente=head.siguiente;
cabeza.siguiente = p;
tamaño++;
}
devolver verdadero;
}
}