Dada una lista enlazada, compruebe si la lista enlazada tiene un bucle o no. El siguiente diagrama muestra una lista enlazada con un bucle.
Las siguientes son diferentes maneras de hacer esto.
Solución 1: enfoque hash:
Recorra la lista una por una y siga poniendo las direcciones de los Nodes en una tabla hash. En cualquier momento, si se llega a NULL, devuelve falso, y si el siguiente de los Nodes actuales apunta a cualquiera de los Nodes previamente almacenados en Hash, devuelve verdadero.
C++
// C++ program to detect loop in a linked list
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
};
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = new Node;
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// Returns true if there is a loop in linked list
// else returns false.
bool detectLoop(struct Node* h)
{
unordered_set<Node*> s;
while (h != NULL) {
// If this node is already present
// in hashmap it means there is a cycle
// (Because you we encountering the
// node for the second time).
if (s.find(h) != s.end())
return true;
// If we are seeing the node for
// the first time, insert it in hash
s.insert(h);
h = h->next;
}
return false;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);
/* Create a loop for testing */
head->next->next->next->next = head;
if (detectLoop(head))
cout << "Loop found";
else
cout << "No Loop";
return 0;
}
// This code is contributed by Geetanjali
Loop found
Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesita un recorrido del bucle. - Espacio Auxiliar: O(n).
n es el espacio requerido para almacenar el valor en hashmap.
Solución 2 : este problema se puede resolver sin hashmap modificando la estructura de datos de la lista enlazada.
Enfoque: Esta solución requiere modificaciones a la estructura de datos básica de la lista enlazada.
- Tenga una bandera visitada con cada Node.
- Recorra la lista enlazada y siga marcando los Nodes visitados.
- Si vuelve a ver un Node visitado, hay un bucle. Esta solución funciona en O(n) pero requiere información adicional con cada Node.
- Se puede implementar una variación de esta solución que no requiere modificar la estructura de datos básica utilizando un hash, simplemente almacene las direcciones de los Nodes visitados en un hash y si ve una dirección que ya existe en el hash, entonces hay un bucle.
C++
// C++ program to detect loop in a linked list
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
int flag;
};
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = new Node;
/* put in the data */
new_node->data = new_data;
new_node->flag = 0;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// Returns true if there is a loop in linked list
// else returns false.
bool detectLoop(struct Node* h)
{
while (h != NULL) {
// If this node is already traverse
// it means there is a cycle
// (Because you we encountering the
// node for the second time).
if (h->flag == 1)
return true;
// If we are seeing the node for
// the first time, mark its flag as 1
h->flag = 1;
h = h->next;
}
return false;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);
/* Create a loop for testing */
head->next->next->next->next = head;
if (detectLoop(head))
cout << "Loop found";
else
cout << "No Loop";
return 0;
}
// This code is contributed by Geetanjali
Loop found
Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesita un recorrido del bucle. - Espacio Auxiliar: O(1).
No se necesita espacio adicional.
Solución 3
: enfoque del algoritmo de búsqueda de ciclos de Floyd : este es el método más rápido y se describe a continuación:
- Recorra la lista enlazada usando dos punteros.
- Mueva un puntero (slow_p) por uno y otro puntero (fast_p) por dos.
- Si estos punteros se encuentran en el mismo Node, entonces hay un bucle. Si los punteros no se encuentran, la lista enlazada no tiene un bucle.
La siguiente imagen muestra cómo funciona la función detectloop en el código:
Implementación del algoritmo de búsqueda de ciclos de Floyd:
C++
// C++ program to detect loop in a linked list
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
class Node {
public:
int data;
Node* next;
};
void push(Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = new Node();
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
int detectLoop(Node* list)
{
Node *slow_p = list, *fast_p = list;
while (slow_p && fast_p && fast_p->next) {
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (slow_p == fast_p) {
return 1;
}
}
return 0;
}
/* Driver code*/
int main()
{
/* Start with the empty list */
Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);
/* Create a loop for testing */
head->next->next->next->next = head;
if (detectLoop(head))
cout << "Loop found";
else
cout << "No Loop";
return 0;
}
// This is code is contributed by rathbhupendra
Loop found
Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesita un recorrido del bucle. - Espacio Auxiliar: O(1).
No se requiere espacio.
¿Cómo funciona el algoritmo anterior?
Consulte: ¿Cómo funciona el enfoque de punteros rápidos y lentos de Floyd?
https://www.youtube.com/watch?v=Aup0kOWoMVg
Solución 4 : marcar los Nodes visitados sin modificar la estructura de datos de la lista enlazada
En este método, se crea un Node temporal. El siguiente puntero de cada Node que se atraviesa apunta a este Node temporal. De esta forma estamos usando el siguiente puntero de un Node como bandera para indicar si el Node ha sido atravesado o no. Cada Node se comprueba para ver si el siguiente apunta a un Node temporal o no. En el caso del primer Node del bucle, la segunda vez que lo recorremos esta condición será cierta, por lo que encontramos que el bucle existe. Si nos encontramos con un Node que apunta a nulo, entonces el ciclo no existe.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to return first node of loop
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* next;
};
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
// A utility function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->key << " ";
head = head->next;
}
cout << endl;
}
// Function to detect first node of loop
// in a linked list that may contain loop
bool detectLoop(Node* head)
{
// Create a temporary node
Node* temp = new Node;
while (head != NULL) {
// This condition is for the case
// when there is no loop
if (head->next == NULL) {
return false;
}
// Check if next is already
// pointing to temp
if (head->next == temp) {
return true;
}
// Store the pointer to the next node
// in order to get to it in the next step
Node* nex = head->next;
// Make next point to temp
head->next = temp;
// Get to the next node in the list
head = nex;
}
return false;
}
/* Driver program to test above function*/
int main()
{
Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(5);
/* Create a loop for testing(5 is pointing to 3) */
head->next->next->next->next->next = head->next->next;
bool found = detectLoop(head);
if (found)
cout << "Loop Found";
else
cout << "No Loop";
return 0;
}
Loop Found
Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesita un recorrido del bucle. - Espacio Auxiliar: O(1).
No se requiere espacio.
Solución 5: Longitud de la tienda
En este método, se crean dos punteros, primero (siempre apunta a la cabeza) y último. Cada vez que se mueve el último puntero, calculamos el número de Nodes entre el primero y el último y comprobamos si el número actual de Nodes es > el número anterior de Nodes; en caso afirmativo, procedemos moviendo el último puntero; de lo contrario, significa que hemos llegado al final del bucle. , por lo que devolvemos la salida en consecuencia.
C++
// C++ program to return first node of loop
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* next;
};
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
// A utility function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->key << " ";
head = head->next;
}
cout << endl;
}
/*returns distance between first and last node every time
* last node moves forwards*/
int distance(Node* first, Node* last)
{
/*counts no of nodes between first and last*/
int counter = 0;
Node* curr;
curr = first;
while (curr != last) {
counter += 1;
curr = curr->next;
}
return counter + 1;
}
// Function to detect first node of loop
// in a linked list that may contain loop
bool detectLoop(Node* head)
{
// Create a temporary node
Node* temp = new Node;
Node *first, *last;
/*first always points to head*/
first = head;
/*last pointer initially points to head*/
last = head;
/*current_length stores no of nodes between current
* position of first and last*/
int current_length = 0;
/*current_length stores no of nodes between previous
* position of first and last*/
int prev_length = -1;
while (current_length > prev_length && last != NULL) {
// set prev_length to current length then update the
// current length
prev_length = current_length;
// distance is calculated
current_length = distance(first, last);
// last node points the next node
last = last->next;
}
if (last == NULL) {
return false;
}
else {
return true;
}
}
/* Driver program to test above function*/
int main()
{
Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(5);
/* Create a loop for testing(5 is pointing to 3) */
head->next->next->next->next->next = head->next->next;
bool found = detectLoop(head);
if (found)
cout << "Loop Found";
else
cout << "No Loop Found";
return 0;
}
Loop Found
Análisis de Complejidad:
- Complejidad temporal: O(n 2 )
- Espacio Auxiliar: O(1)
Otro enfoque:
- Este es el enfoque más simple del problema dado, lo único que tenemos que hacer es asignar un nuevo valor a cada dato de Node en la lista enlazada que no está en el rango dado.
- Ejemplos Supongamos (1 <= Datos en el Node <= 10 ^ 3) luego, después de visitar el Node, asigne los datos como -1 ya que están fuera del rango dado.
Siga el código que se proporciona a continuación para una mejor comprensión:
C++
// C++ program to return first node of loop
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* next;
};
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
// Function to detect first node of loop
// in a linked list that may contain loop
bool detectLoop(Node* head)
{
// If the head is null we will return false
if (!head)
return 0;
else {
// Traversing the linked list
// for detecting loop
while (head) {
// If loop found
if (head->key == -1) {
return true;
}
// Changing the data of visited node to any
// value which is outside th given range here it
// is supposed the given range is (1 <= Data on
// Node <= 10^3)
else {
head->key = -1;
head = head->next;
}
}
// If loop not found return false
return 0;
}
}
/* Driver program to test above function*/
int main()
{
Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(5);
/* Create a loop for testing(5 is pointing to 3) */
head->next->next->next->next->next = head->next->next;
bool found = detectLoop(head);
cout << found << endl;
return 0;
}
1
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Consulte el artículo completo sobre Detectar bucle en una lista vinculada para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA