Esta é uma pergunta de teste clássica escrita pela Microsoft. Os dois ponteiros h1 e h2 percorrem a lista vinculada individualmente desde o início, h1 avança 1 passo de cada vez e h2 avança 2 passos de cada vez. ring does not exist ; Se h2 tocar h1 que deveria estar atrás dele, significa que existe um loop (ou seja, ocorre um loop).
Se o anel não existir, h2 deverá encontrar NULL primeiro:
Se o anel existir, h2 e h1 definitivamente se encontrarão, e o ponto de encontro está dentro do anel: h2 atravessa mais rápido que h1 e definitivamente não se encontrará no início da lista vinculada sem anel, então quando h1 e h2 entram o anel Finalmente, cada movimento de h2 reduzirá a lacuna entre h2 e h1 na direção direta em 1. Finalmente, a lacuna entre h1 e h2 será reduzida a 0, ou seja, eles se encontram.
public static void main(String args[]){
ListaSingleList = new SingleList();
for(int i=0;i<100;i++){
lista.add(i);
}
System.out.print(SingleList.isExistingLoop(lista));
}
}
Nó público (valor do objeto){
este.dados = valor;
}
publicNode(){
isto.dados=nulo;
isto.próximo = null;
}
}
inicialização privada void(){
este.tamanho = 0;
this.head = new Node();
}
public SingleList(){
iniciar();
}
public boolean contém(Valor do objeto){
sinalizador booleano = falso;
Nó p = head.next;
enquanto(p!=nulo){
if(valor.equals(p.dados)){
bandeira = verdadeiro;
quebrar;
}outro(
p = p.próximo;
)
}
bandeira de retorno;
}
public boolean add(Valor do objeto){
if(contém(valor))
retornar falso;
outro{
Nó p = novo Nó(valor);
p.próximo=cabeça.próximo;
cabeça.próximo = p;
tamanho++;
}
retornar verdadeiro;
}
}