Detectar um loop em uma lista encadeada em C++

O nó final de uma lista vinculada que possui um loop se referirá a outro nó na mesma lista em vez de NULL. Se houver um nó em uma lista vinculada que pode ser acessado repetidamente seguindo o próximo ponteiro, a lista é considerada tem um ciclo.

Normalmente, o último nó da lista encadeada refere-se a uma referência NULL para denotar a conclusão da lista. No entanto, em uma lista vinculada com um loop, o nó final da lista refere-se a um nó inicial, a um nó interno ou a si mesmo. Portanto, nessas circunstâncias, devemos identificar e encerrar o loop definindo a referência do próximo nó como NULL. A parte de detecção do loop em uma lista encadeada é explicada neste artigo.

Em C++, existem várias maneiras de localizar loops em uma lista encadeada:

Abordagem baseada em tabela de hash : esta abordagem armazena os endereços dos nós visitados em uma tabela hash. Um loop na lista encadeada existe se um nó já estiver presente na tabela hash quando for visitado novamente.

Abordagem do ciclo de Floyd : o algoritmo “tartaruga e lebre”, comumente conhecido como algoritmo de detecção de ciclo de Floyd: esta técnica utiliza dois ponteiros, um movendo-se mais lentamente que o outro e o outro movendo-se mais rapidamente. O ponteiro mais rápido acabará ultrapassando o ponteiro mais lento se houver um loop na lista encadeada, revelando a existência do loop.

Método recursivo : esse método percorre a lista encadeada chamando a si mesmo várias vezes. A lista vinculada contém um loop se o nó atual tiver sido visitado anteriormente.

Abordagem baseada em pilha : esta abordagem armazena os endereços dos nós visitados em uma pilha. Um loop na lista encadeada está presente se um nó já estiver na pilha quando for visitado novamente.

Vamos explicar cada abordagem em detalhes para entender o conceito.

Abordagem 1: Abordagem HashSet

Utilizar hashing é o método mais direto. Aqui, percorremos a lista uma a uma enquanto mantemos uma tabela hash com os endereços dos nós. Portanto, existe um loop se alguma vez passarmos pelo próximo endereço do nó atual que já está contido na tabela de hash. Caso contrário, não haverá loop na Lista Vinculada se chegarmos a NULL (ou seja, atingir o final da Lista Vinculada).

Será muito fácil implementar esta estratégia.

Ao percorrer a lista vinculada, utilizaremos um unordered_hashmap e continuaremos adicionando nós a ele.

Agora, ao nos depararmos com um nó que já está representado no mapa, saberemos que chegamos ao início do loop.

• • Além disso, mantivemos dois ponteiros a cada passo, headNode apontando para o nó atual e lastNode apontando para o nó anterior do nó atual, durante a iteração.
  • Como nosso headNode agora está apontando para o nó inicial do loop e como lastNode estava apontando para o nó para o qual a cabeça estava apontando (ou seja, está se referindo ao lastNode do loop), nosso headNode está atualmente apontando para o nó inicial do loop.
  • O loop será interrompido definindo l astNode->next == NULL .

Ao fazer isso, o nó final do loop, em vez de se referir ao nó inicial do loop, começa a apontar para NULL.

A complexidade média de tempo e espaço do método de hash é O(n). O leitor deve sempre estar ciente de que a implementação do Hashing DataStructure embutido na linguagem de programação determinará a complexidade de tempo total no caso de uma colisão no hashing.

Implementação do programa C++ para o método acima (HashSet):

Saída:

A explicação passo a passo do código é fornecida abaixo:

1. 1. O arquivo de cabeçalho bits/stdc++.h>, que contém todas as bibliotecas C++ comuns, está incluído no código.
   2. Uma estrutura chamada “Node” é construída e possui dois membros: uma referência ao próximo nodo na lista e um inteiro chamado “value”.
   3. Com um valor inteiro como entrada e o ponteiro “próximo” definido como NULL, a função “newNode” cria um novo nó com esse valor.
   4. A função ' funçãoHashMap' é definido, o que leva um ponteiro para o nó principal da lista encadeada como entrada.
   5. Dentro de ' functionHashMap ' , um unordered_map chamado 'hash_map' é criado, que é usado para implementar uma estrutura de dados de mapa hash.
   6. Um ponteiro para o último nó da lista é inicializado como NULL.
   7. Um loop while é usado para percorrer a lista encadeada, que começa no nó principal e continua até que o nó principal seja NULL.
   8. O ponteiro lastNode é atualizado para o nó atual dentro do loop while se o nó atual (headNode) ainda não estiver presente no mapa de hash.
   9. Se o nó atual for encontrado no mapa, significa que um loop está presente na lista encadeada. Para remover o loop, o próximo ponteiro do lastNode está configurado para NULO e o loop while é interrompido.
   10. O nó principal da lista encadeada é usado como entrada para uma função chamada “display”, que exibe o valor de cada nó na lista do começo ao fim.
   11. No principal função, criando um loop.
   12. A função ‘functionHashMap’ é chamada com o ponteiro headNode como entrada, que remove o loop da lista.
   13. A lista modificada é exibida usando a função ‘display’.

Abordagem 2: Ciclo de Floyd

O algoritmo de detecção de ciclos de Floyd, geralmente conhecido como algoritmo da tartaruga e da lebre, fornece a base para esse método de localização de ciclos em uma lista encadeada. O ponteiro “lento” e o ponteiro “rápido”, que percorrem a lista em várias velocidades, são os dois ponteiros usados ​​nesta técnica. O ponteiro rápido avança duas etapas, enquanto o ponteiro lento avança uma etapa a cada iteração. Um ciclo na lista encadeada existe se os dois pontos ficarem frente a frente.

1. Com o nó principal da lista vinculada, inicializamos dois ponteiros chamados rápido e lento.

2. Agora executamos um loop para percorrer a lista encadeada. O ponteiro rápido deve ser movido dois locais à frente do ponteiro lento a cada etapa da iteração.

3. Não haverá um loop na lista vinculada se o ponteiro rápido atingir o final da lista (fastPointer == NULL ou fastPointer->next == NULL). Caso contrário, os ponteiros rápido e lento eventualmente se encontrarão, o que significa que a lista encadeada tem um loop.

Implementação do programa C++ para o método acima (Ciclo de Floyd):

Saída:

Explicação:

1. 1. Os cabeçalhos relevantes, como “bits/stdc++.h” e “std::cout,” são incluídos primeiro.
   2. A estrutura “Node”, que representa um nó na lista encadeada, é então declarada. Um próximo ponteiro que leva ao nó seguinte na lista é incluído junto com um campo de dados inteiros em cada nó.
   3. Em seguida, define “deleteLoop” e “detectAndDeleteLoop”, duas funções. Um loop é removido de uma lista vinculada usando o primeiro método e um loop é detectado na lista usando a segunda função, que então chama o primeiro procedimento para remover o loop.
   4. Uma nova lista vinculada com cinco nós é criada na função principal e um loop é estabelecido definindo o próximo ponteiro do último nó para o terceiro nó.
   5. Em seguida, ele faz uma chamada para o método “detectAndDeleteLoop” enquanto passa o nó principal da lista vinculada como um argumento. Para identificar loops, esta função usa a abordagem “Ponteiros lentos e rápidos”. Ele emprega dois ponteiros que começam no topo da lista, slowPTR e fastPTR. Enquanto o ponteiro rápido move dois nós ao mesmo tempo, o ponteiro lento move apenas um nó por vez. O ponteiro rápido acabará ultrapassando o ponteiro lento se a lista contiver um loop e os dois pontos colidirão no mesmo nó.
   6. A função invoca a função “deleteLoop” se encontrar um loop, fornecendo o nó principal da lista e a interseção dos ponteiros lento e rápido como entradas. Este procedimento estabelece dois ponteiros, ptr1 e ptr2, para o nó principal da lista e conta o número de nós no loop. Em seguida, avança um ponteiro k nós, onde k é o número total de nós no loop. Então, até que eles se encontrem no início do loop, ele avança os dois pontos, um nó por vez. O loop é então interrompido definindo o próximo ponteiro do nó no final do loop como NULL.
   7. Depois de remover o loop, ele exibe a lista encadeada como uma etapa final.

Abordagem 3: Recursão

A recursão é uma técnica para resolver problemas particionando-os em subproblemas menores e mais fáceis. A recursão pode ser usada para percorrer uma lista encadeada individualmente no caso de um loop ser encontrado executando continuamente uma função para o próximo nó na lista até que o final da lista seja alcançado.

Em uma lista encadeada individualmente, o princípio básico por trás do uso da recursão para encontrar um loop é começar no início da lista, marcar o nó atual como visitado em cada etapa e, em seguida, ir para o próximo nó invocando recursivamente a função para esse nó. O método irá iterar na lista encadeada completa porque é chamado recursivamente.

A lista contém um loop se um nó que foi previamente marcado como visitado for encontrado pela função; neste caso, a função pode retornar true. O método pode retornar falso se chegar ao final da lista sem passar por um nó visitado, o que indica que não há loop.

Embora essa técnica de utilização de recursão para encontrar um loop em uma única lista encadeada seja simples de usar e compreender, ela pode não ser a mais eficaz em termos de complexidade de tempo e espaço.

Implementação do programa C++ para o método acima (Recursão):

Saída:

Explicação:

1. 1. A função detectarLoopLinkedList() neste programa aceita o cabeçalho da lista encadeada como uma entrada.
   2. A recursão é usada pela função para iterar na lista encadeada. Como caso básico para a recursão, ela começa determinando se o nó atual é NULL. Em caso afirmativo, o método retorna false, indicando que não existe nenhum loop.
   3. O valor da propriedade “visited” do nó atual é então verificado para ver se ele já foi visitado anteriormente. Retorna true se foi visitado, sugerindo que um loop foi encontrado.
   4. A função marca o nó atual como visitado se já tiver sido visitado alterando sua propriedade “visited” para true.
   5. O valor da variável visitada é então verificado para ver se o nó atual foi visitado anteriormente. Se já foi usado antes, deve existir um loop e a função retorna true.
   6. Por fim, a função chama a si mesma com o próximo nó da lista, passando headNode->próximo como argumento. Recursivamente , isso é realizado até que um loop seja encontrado ou todos os nós tenham sido visitados. Significa que a função define a variável visitada como verdadeira se o nó atual nunca foi visitado antes de se chamar recursivamente para o próximo nó na lista encadeada.
   7. O código constrói três nós e os une para produzir uma lista encadeada no função principal . O método detectarLoopLinkedList() é então invocado no nó principal da lista. O programa produz “ Loop deduzido na lista encadeada ' se detectarLoopLinkedList() retorna verdadeiro; caso contrário, ele emite “ Nenhum loop detectado na lista encadeada “.
   8. O código então insere um loop na lista encadeada definindo o próximo ponteiro do último nó para o segundo nó. Então, dependendo do resultado da função, ele executa detectarLoopLinkedList() novamente e produz ' Loop deduzido na lista encadeada ' ou ' Nenhum loop detectado na lista encadeada .”

Abordagem 4: Usando Pilha

Os loops em uma lista encadeada podem ser encontrados usando uma pilha e o método de “pesquisa em profundidade” (DFS). O conceito fundamental é iterar pela lista encadeada, colocando cada nó na pilha se ainda não tiver sido visitado. Um loop é reconhecido se um nó que já está na pilha for encontrado novamente.

Aqui está uma breve descrição do procedimento:

1. 1. Crie uma pilha vazia e uma variável para registrar os nós que foram visitados.
   2. Empurre a lista encadeada para a pilha, começando no topo. Anote que a cabeça foi visitada.
   3. Empurre o próximo nó da lista para a pilha. Adicione uma marca de visita a este nó.
   4. Ao percorrer a lista, coloque cada novo nó na pilha para indicar que ele foi visitado.
   5. Verifique se um nó que foi visitado anteriormente está no topo da pilha, caso seja encontrado. Em caso afirmativo, um loop foi encontrado e o loop é identificado pelos nós na pilha.
   6. Retire os nós da pilha e continue percorrendo a lista se nenhum loop for encontrado.

Implementação do programa C++ para o método acima (Pilha)

Saída:

Explicação:

Este programa usa uma pilha para descobrir se uma lista encadeada individualmente tem um loop.

• 1. A biblioteca de fluxo de entrada/saída e a biblioteca de pilha estão presentes na primeira linha.

  2. O namespace padrão está incluído na segunda linha, permitindo-nos acessar as funções da biblioteca de fluxo de entrada/saída sem precisar prefixá-las com “std::.”

  3. A linha a seguir define o struct Node, que consiste em dois membros: um inteiro chamado “data” e um ponteiro para outro Node chamado “next”.

  4. O cabeçalho da lista encadeada é uma entrada para o método detectLoopLinkedList(), que é definido na próxima linha. A função produz um valor booleano que indica se um loop foi encontrado ou não.

  5. Uma pilha de ponteiros de Node chamada “stack” e um ponteiro para um Node chamado “tempNode” que é inicializado com o valor de headNode são ambos criados dentro da função.

  6. Então, desde que tempNode não seja um ponteiro nulo, entramos em um loop while.

  (a) O elemento superior da pilha deve corresponder ao nó atual para que possamos determinar que ele não está vazio. Retornamos true se este for o caso porque um loop foi encontrado.

  (b) Se a condição acima for falsa, o ponteiro do nó atual é colocado na pilha e tempNode é definido como o nó seguinte na lista encadeada.

  7. Retornamos false após o loop while porque nenhum loop foi observado.

  8. Construímos três objetos Node e os inicializamos na função main(). Como não há loop no primeiro exemplo, definimos os ponteiros “próximos” de cada nó corretamente.

Conclusão:

Em conclusão, o melhor método para detectar loops em uma lista encadeada depende do caso de uso específico e das restrições do problema. A Hash Table e o algoritmo de descoberta de ciclos de Floyd são métodos eficientes e amplamente utilizados na prática. Stack e recursão são métodos menos eficientes, mas são mais intuitivos.