Detectar un bucle en una lista vinculada en C ++

El nodo final de una lista vinculada que tiene un bucle se referirá a otro nodo en la misma lista en lugar del nulo.Si hay un nodo en una lista vinculada a la que se puede acceder repetidamente siguiendo el siguiente puntero, se dice que la lista tiene un ciclo.

Por lo general, el último nodo de la lista vinculada se refiere a una referencia nula para denotar la conclusión de la lista. Sin embargo, en una lista vinculada con un bucle, el nodo final de la lista se refiere a un nodo de inicio, un nodo interno o sí mismo. Por lo tanto, en tales circunstancias, debemos identificar y terminar el bucle estableciendo la referencia del siguiente nodo a NULL. La parte de detección del bucle en una lista vinculada se explica en este artículo.

En C ++, hay numerosas formas de encontrar bucles en una lista vinculada:

Enfoque basado en la mesa hash: Este enfoque almacena las direcciones de los nodos visitados en una tabla hash. Existe un bucle en la lista vinculada si un nodo ya está presente en la tabla hash cuando se vuelve a visitar.

Enfoque del ciclo de Floyd: El algoritmo "Tortoise and Hare", comúnmente conocido como algoritmo de búsqueda de ciclo de Floyd: esta técnica utiliza dos punteros, uno que se mueve más lentamente que el otro y el otro que se mueve más rápidamente. El puntero más rápido superará en última instancia el puntero más lento si hay un bucle en la lista vinculada, revelando la existencia del bucle.

Método recursivo: Este método pasa por la lista vinculada llamándose una y otra vez. La lista vinculada contiene un bucle si el nodo actual se ha visitado previamente.

Enfoque basado en pila: Este enfoque almacena las direcciones de los nodos visitados en una pila. Un bucle en la lista vinculada está presente si un nodo ya está allí en la pila cuando se vuelve a visitar.

Expliquemos cada enfoque en detalle para comprender el concepto.

Enfoque 1: enfoque hashset

Utilizar el hashing es el método más directo. Aquí, revisamos la lista uno por uno mientras mantenemos una tabla hash con las direcciones de nodo. Por lo tanto, existe un bucle si alguna vez nos encontramos con la siguiente dirección del nodo actual que ya está contenido en la tabla hash. De lo contrario, no hay bucle en la lista vinculada si nos encontramos con nulo (i.mi., llegar al final de la lista vinculada).

Será bastante fácil implementar esta estrategia.

Mientras atraviesa la lista vinculada, utilizaremos un desordenado_hashmap y seguiremos agregando nodos.

Ahora, una vez que nos encontremos con un nodo que ya se muestra en el mapa, sabremos que hemos llegado al comienzo del bucle.

• • Además, mantuvimos dos punteros en cada paso, noble señalando el nodo actual y último señalando el nodo anterior del nodo actual, mientras itera.
  • Como el nuestro noble ahora apunta al nodo de inicio del bucle y como último estaba señalando el nodo al que estaba apuntando la cabeza (yo.mi., se refiere al último del bucle), nuestro noble Actualmente apunta al nodo de inicio del bucle.
  • El bucle se romperá configurando Lastnode-> next == null.

Al hacer esto, el nodo de bucle final en lugar de referirse al nodo inicial del bucle comienza a señalar a NULL.

El tiempo promedio y la complejidad del espacio del método hash es o (n). El lector siempre debe ser consciente de que la implementación de la datos de hashing incorporada en el lenguaje de programación determinará la complejidad del tiempo total en caso de una colisión en el hashing.

Implementación del programa C ++ para el método anterior (hashset):

#incluir
usando el espacio de nombres STD;
nodo de estructura
valor int;
nodo de estructura* Siguiente;
;
Nodo* Newnode (int value)

Nodo* tempNode = nuevo nodo;
tempnode-> valor = valor;
tempnode-> next = null;
return tempnode;

// identificar y eliminar cualquier bucle potencial
// en una lista vinculada con esta función.
FunctionHashMap (nodo* nodo)

// Creó un MAPS de UNDERSED_MAP para implementar el mapa hash
desordenable_map hash_map;
// puntero a lastNode
Nodo* LastNode = null;
mientras (nodo != Nulo)
// Si falta un nodo en el mapa, agrégalo.
if (hash_map.find (headNode) == hash_map.fin())
hash_map [headNode] ++;
dastNode = headNode;
headNode = headNode-> next;

// Si hay un ciclo presente, establezca el siguiente puntero del nodo final en NULL.
demás
dastNode-> next = null;
romper;



// Muestra la lista vinculada
pantalla vacía (nodo* nodo)

mientras (nodo != Nulo)
cout headNode = headNode-> next;

cout << endl;

/* Función principal*/
int main ()

Nodo* headNode = newnode (48);
headNode-> next = headNode;
headNode-> next = newnode (18);
headNode-> next-> next = newnode (13);
headNode-> next-> next-> next = newnode (2);
headNode-> next-> next-> next-> next = newnode (8);
/ * Crear un bucle en LinkedList */
headNode-> next-> next-> next-> next-> next = headNode-> next-> next;
functionHashMap (HeadNode);
printf ("Lista vinculada sin bucle \ n");
visualización (headNode);
regresar 0;

Producción:

Lista vinculada sin bucle
48 18 13 2 8

La explicación paso a paso del código se proporciona a continuación:

1. 1. Los bits/stdc++.H> El archivo de encabezado, que contiene todas las bibliotecas C ++ comunes, se incluye en el código.
   2. Se construye una estructura llamada "nodo", y tiene dos miembros: una referencia al siguiente nodo en la lista y un entero llamado "Valor."
   3. Con un valor entero como su entrada y el "siguiente" puntero establecido en NULL, la función "Newnode" crea un nuevo nodo con ese valor.
   4. La función 'functionHashMap ' se define, que toma un puntero al nodo principal de la lista vinculada como entrada.
   5. Dentro de 'functionHashmap'Función, se crea un_map de ORDEREDIME' Hash_Map ', que se utiliza para implementar una estructura de datos de mapa hash.
   6. Un puntero al último nodo de la lista se inicializa a NULL.
   7. Se usa un bucle de tiempo para atravesar la lista vinculada, que comienza desde el nodo de la cabeza y continúa hasta que el nodo de la cabeza esté nulo.
   8. El puntero de LastNode se actualiza al nodo actual dentro del bucle While si el nodo actual (HeadNode) aún no está presente en el mapa hash.
   9. Si el nodo actual se encuentra en el mapa, significa que hay un bucle presente en la lista vinculada. Para eliminar el bucle, el siguiente puntero del último se establece en NULO y el bucle mientras está roto.
   10. El nodo principal de la lista vinculada se usa como entrada para una función llamada "Display", que genera el valor de cada nodo en la lista de principio a fin.
   11. En el principal función, creando un bucle.
   12. La función 'functionHashMap' se llama con el puntero del notodo como entrada, que elimina el bucle de la lista.
   13. La lista modificada se muestra utilizando la función 'Mostrar'.

Enfoque 2: ciclo de Floyd

El algoritmo de detección de ciclo de Floyd, a menudo conocido como la tortuga y el algoritmo Hare, proporciona la base para este método de localización de ciclos en una lista vinculada. El puntero "lento" y el puntero "rápido", que atraviesa la lista a varias velocidades, son los dos punteros utilizados en esta técnica. El puntero rápido avanza dos pasos, mientras que el puntero lento avanza un paso cada iteración. Existe un ciclo en la lista vinculada si los dos puntos se enfrentan cara a cara.

1. Con el nodo principal de la lista vinculada, inicializamos dos punteros llamados Fast and Slow.

2. Ahora ejecutamos un bucle para movernos a través de la lista vinculada. El puntero rápido debe moverse dos ubicaciones frente al puntero lento en el paso de cada iteración.

3. No habrá un bucle en la lista vinculada si el puntero rápido alcanza el final de la lista (fastPointer == null o fastpointer-> next == null). Si no, los punteros rápidos y lentos eventualmente se reunirán, lo que significa que la lista vinculada tiene un bucle.

Implementación del programa C ++ para el método anterior (ciclo de Floyd):

#incluir
usando el espacio de nombres STD;
/ * Nodo de lista de enlaces */
nodo de estructura
datos int;
nodo de estructura* Siguiente;
;
/* Función para eliminar el bucle. */
void deleteloop (nodo de struct*, nodo struct*);
/* Esta función localiza y elimina los bucles de la lista. Rinde 1
Si había un bucle en la lista; más, devuelve 0. */
int

struct node *lentoPtr = list, *fastPtr = list;
// iterar para verificar si el bucle está ahí.
while (slowptr && fastptr && fastptr-> next)
SlowPtr = SlowPtr-> Siguiente;
fastPtr = fastPtr-> next-> next;
/* Si SlowPtr y FastPtr se encuentran en algún momento, entonces allí
es un bucle */
if (slowptr == fastPtr)
deleteloop (slowptr, lista);
/* Regresar 1 para indicar que se ha descubierto un bucle. */
regresar 1;


/* Devolver 0 para indicar que no se ha descubierto ningún bucle.*/
regresar 0;

/* Función para eliminar el bucle de la lista vinculada.
Loopnode apunta a uno de los nodos de bucle y el noto del encendido está apuntando
al nodo de inicio de la lista vinculada */
Void DeletELOOP (Struct Node* Loopnode, Nodode Struct* HeadNode)

struct nodo* ptr1 = loopnode;
struct nodo* ptr2 = loopnode;
// Cuenta cuántos nodos hay en el bucle.
Unsigned int k = 1, i;
Mientras (Ptr1-> Siguiente != ptr2)
ptr1 = ptr1-> next;
K ++;

// arregla un puntero al nodo de cabeza
ptr1 = headNode;
// y el otro puntero a k nodos después del nodo de cabeza
ptr2 = headNode;
para (i = 0; i < k; i++)
ptr2 = ptr2-> next;
/* Cuando ambos puntos se mueven simultáneamente,
chocarán en el nodo inicial del bucle. */
Mientras (PTR2 != ptr1)
ptr1 = ptr1-> next;
ptr2 = ptr2-> next;

// Obtener el último puntero del nodo.
mientras (Ptr2-> Siguiente != Ptr1)
ptr2 = ptr2-> next;
/* Para cerrar el bucle, establezca el posterior
nodo al nodo de terminación del bucle. */
ptr2-> next = null;

/ * Función para mostrar la lista vinculada */
Void DisplayLinkedList (nodo de nodo* struct)

// Muestra la lista vinculada después de eliminar el bucle
mientras (nodo != Nulo)
cout nodo = nodo-> next;


struct node* newnode (int key)

struct node* temp = new Node ();
temp-> data = key;
temp-> next = null;
regresar temp;

// Código principal
int main ()

struct node* headNode = newnode (48);
headNode-> next = newnode (18);
headNode-> next-> next = newnode (13);
headNode-> next-> next-> next = newnode (2);
headNode-> next-> next-> next-> next = newnode (8);
/ * Crear un bucle */
headNode-> next-> next-> next-> next-> next = headNode-> next-> next;
// Muestra el bucle en la lista vinculada
// DisplayLinkedList (HeadNode);
detectanddeletelop (nodo de cabeza);
cout << "Linked List after no loop \n";
DisplayLinkedList (HeadNode);
regresar 0;

Producción:

Lista vinculada después de ningún bucle
48 18 13 2 8

Explicación:

1. 1. Los encabezados relevantes, como "bits/stdc++.h "y" std :: cout "se incluyen por primera vez.
   2. La estructura "nodo", que significa un nodo en la lista vinculada, se declara luego. Se incluye un siguiente puntero que conduce al siguiente nodo en la lista junto con un campo de datos enteros en cada nodo.
   3. Luego, define "Deleteloop" y "DetectAndDeletelop", dos funciones. Se elimina un bucle de una lista vinculada utilizando el primer método, y se detecta un bucle en la lista utilizando la segunda función, que luego llama al primer procedimiento para eliminar el bucle.
   4. Se crea una nueva lista vinculada con cinco nodos en la función principal, y se establece un bucle configurando el próximo puntero del último nodo en el tercer nodo.
   5. Luego hace una llamada al método "DetectAndDeletElEloop" al pasar el nodo principal de la lista vinculada como argumento. Para identificar bucles, esta función usa el enfoque de "punteros lentos y rápidos". Emplea dos punteros que comienzan en la parte superior de la lista, Slowptr y FastPtr. Mientras que el puntero rápido mueve dos nodos a la vez, el puntero lento solo mueve un nodo a la vez. El puntero rápido finalmente superará el puntero lento si la lista contiene un bucle, y los dos puntos chocarán en el mismo nodo.
   6. La función invoca la función "deleteloop" si encuentra un bucle, suministrando el nodo principal de la lista y la intersección de los punteros lentos y rápidos como entradas. Este procedimiento establece dos punteros, PTR1 y PTR2, al nodo principal de la lista y cuenta el número de nodos en el bucle. Después de eso, avanza un puntero K nodos, donde K es el número total de nodos en el bucle. Luego, hasta que se encuentren al comienzo del circuito, avanza ambos puntos un nodo a la vez. Luego se rompe el bucle configurando el siguiente puntero del nodo al final del bucle a NULL.
   7. Después de eliminar el bucle, muestra la lista vinculada como un paso final.

Enfoque 3: Recursión

La recursión es una técnica para resolver problemas al dividirlos en subproblemas más pequeños y más fáciles. La recursión se puede utilizar para atravesar una lista vinculada individualmente en caso de que se encuentre un bucle ejecutando continuamente una función para el siguiente nodo en la lista hasta que se alcance el final de la lista.

En una lista vinculada individualmente, el principio básico detrás del uso de la recursión para encontrar un bucle es comenzar en el cabezal de la lista, marcar el nodo actual como se ve en cada paso y luego continuar al siguiente nodo invocando recursivamente la función para ese nodo. El método se iterará en la lista vinculada completa porque se llama recursivamente.

La lista contiene un bucle si la función se encuentra un nodo que se ha marcado previamente según lo visitado; En este caso, la función puede devolver verdad. El método puede devolver falso si llega al final de la lista sin ejecutar un nodo visitado, lo que indica que no hay bucle.

Aunque esta técnica para utilizar la recursión para encontrar un bucle en una sola lista vinculada es sencilla de usar y comprender, podría no ser el más efectivo en términos de tiempo y complejidad espacial.

Implementación del programa C ++ para el método anterior (recursión):

#incluir
usando el espacio de nombres STD;
nodo de estructura
datos int;
Nodo* siguiente;
Bool visitó;
;
// función de detección de bucle de lista vinculada
bool DetectloopLinkedList (nodo* headNode)
if (headNode == null)
falso retorno; // Si la lista vinculada está vacía, el caso básico

// Hay un bucle si el nodo actual tiene
// ya ha sido visitado.
if (headNode-> visitado)
devolver verdadero;

// Agregar una marca de visitas al nodo actual.
HeadNode-> Visited = True;
// llamando al código para el nodo posterior repetidamente
return DetectLoopLinkEdList (HeadNode-> Next);

int main ()
Nodo* headNode = new Node ();
Nodo* SecondNode = new Node ();
Nodo* tercero = nuevo nodo ();
HeadNode-> data = 1;
HeadNode-> next = SecondNode;
HeadNode-> Visited = false;
SecondNode-> data = 2;
SecondNode-> next = ThirdNode;
SecondNode-> Visited = false;
ThirdNode-> data = 3;
ThirdNode-> next = null; // sin bucle
ThirdNode-> Visited = false;
if (DetectLoopLinkedList (HeadNode))
cout << "Loop detected in linked list" << endl;
demás
cout << "No loop detected in linked list" << endl;

// Creando un bucle
ThirdNode-> next = SecondNode;
if (DetectLoopLinkedList (HeadNode))
cout << "Loop detected in linked list" << endl;
demás
cout << "No loop detected in linked list" << endl;

regresar 0;

Producción:

Sin bucle detectado en la lista vinculada
Bucle detectado en la lista vinculada

Explicación:

1. 1. La función detectloopLinkedList () En este programa acepta el jefe de la lista vinculada como una entrada.
   2. La función utiliza la recursión para iterar en la lista vinculada. Como caso básico para la recursión, comienza determinando si el nodo actual es nulo. Si es así, el método devuelve falso, lo que indica que no existe un bucle.
   3. El valor de la propiedad "visitada" del nodo actual se verifica para ver si se ha visitado previamente. Devuelve cierto si se ha visitado, lo que sugiere que se ha encontrado un bucle.
   4. La función marca el nodo actual como se ve si ya se ha visitado cambiando su propiedad "visitada" a verdadero.
   5. Luego se verifica el valor de la variable visitada para ver si el nodo actual se ha visitado previamente. Si se ha utilizado antes, debe existir un bucle y la función devuelve verdaderas.
   6. Por último, la función se llama a sí misma con el siguiente nodo en la lista pasando HeadNode-> Siguiente como argumento. Recursivamente, Esto se lleva a cabo hasta que se encuentra un bucle o se hayan visitado todos los nodos. Significa que la función establece la variable visitada a verdaderas si el nodo actual nunca se ha visitado antes de llamarse recursivamente para el siguiente nodo en la lista vinculada.
   7. El código construye tres nodos y se une a ellos para producir una lista vinculada en el función principal. El método detectloopLinkedList () Luego se invoca en el nodo principal de la lista. El programa produce "Bucle deducido en la lista vinculada" si detectloopLinkedList () devuelve verdadero; más, sale "Sin bucle detectado en la lista vinculada".
   8. El código luego inserta un bucle en la lista vinculada configurando el siguiente puntero del último nodo en el segundo nodo. Luego, dependiendo del resultado de la función, se ejecuta detectloopLinkedList () de nuevo y produce cualquiera de los "Bucle deducido en la lista vinculada" o "Sin bucle detectado en la lista vinculada."

Enfoque 4: Uso de la pila

Los bucles en una lista vinculada se pueden encontrar utilizando una pila y el método "Búsqueda de profundidad" (DFS). El concepto fundamental es iterar a través de la lista vinculada, empujando cada nodo a la pila si aún no se ha visitado. Se reconoce un bucle si se encuentra un nodo que ya está en la pila.

Aquí hay una breve descripción del procedimiento:

1. 1. Crear una pila vacía y una variable para grabar los nodos que se han visitado.
   2. Empuje la lista vinculada a la pila, comenzando en la parte superior. Tome nota de que la cabeza ha sido visitada.
   3. Empuje el siguiente nodo en la lista en la pila. Agregue una marca de visitas a este nodo.
   4. A medida que atraviesa la lista, empuje cada nuevo nodo a la pila para indicar que se ha visitado.
   5. Verifique si un nodo que se ha visitado anteriormente está en la parte superior de la pila si se encuentra. Si es así, se ha encontrado un bucle y los nodos identifican el bucle en la pila.
   6. Aparente los nodos de la pila y siga atravesando la lista si no se encuentra el bucle.

Implementación del programa C ++ para el método anterior (pila)

#incluir
#incluir
usando el espacio de nombres STD;
nodo de estructura
datos int;
Nodo* siguiente;
;
// Función para detectar el bucle en una lista vinculada
bool DetectloopLinkedList (nodo* headNode)
pila pila;
Nodo* tempnode = headNode;
mientras (tempnode != Nulo)
// Si el elemento superior de la pila coincide
// El nodo actual y la pila no está vacía
si (!pila.stack vacía () &&.top () == tempnode)
devolver verdadero;

pila.push (tempnode);
tempnode = tempnode-> next;

falso retorno;

int main ()
Nodo* headNode = new Node ();
Nodo* SecondNode = new Node ();
Nodo* tercero = nuevo nodo ();
HeadNode-> data = 1;
HeadNode-> next = SecondNode;
SecondNode-> data = 2;
SecondNode-> next = ThirdNode;
ThirdNode-> data = 3;
ThirdNode-> next = null; // sin bucle
if (DetectLoopLinkedList (HeadNode))
cout << "Loop detected in linked list" << endl;
demás
cout << "No loop detected in linked list" << endl;

// Creando un bucle
ThirdNode-> next = SecondNode;
if (DetectLoopLinkedList (HeadNode))
cout << "Loop detected in linked list" << endl;
demás
cout << "No loop detected in linked list" << endl;

Producción:

Sin bucle detectado en la lista vinculada
Bucle detectado en la lista vinculada

Explicación:

Este programa usa una pila para averiguar si una lista vinculada individualmente tiene un bucle.

• 1. La biblioteca de transmisión de entrada/salida y la biblioteca de pila están presentes en la primera línea.

  2. El espacio de nombres estándar se incluye en la segunda línea, lo que nos permite acceder a las funciones de la biblioteca de transmisión de entrada/salida sin tener que prefijarlas con "STD ::."

  3. La siguiente línea define el nodo de estructura, que consta de dos miembros: un entero llamado "datos" y un puntero a otro nodo llamado "Siguiente."

  4. El cabezal de la lista vinculada es una entrada para el método DetectloopLinkedList (), que se define en la siguiente línea. La función produce un valor booleano que indica si se encontró o no un bucle.

  5. Una pila de punteros de nodo llamado "pila" y un puntero a un nodo llamado "tempnode" que se inicializa con el valor del nodo se crea dentro de la función.

  6. Entonces, siempre que Tempnode no sea un puntero nulo, entramos en un bucle de tiempo.

  (a) El elemento superior de la pila debe coincidir con el nodo actual para que podamos determinar que no está vacío. Devuelve verdadero si este es el caso porque se ha encontrado un bucle.

  (b) Si la condición mencionada anteriormente es falsa, el puntero del nodo actual se empuja a la pila, y Tempnode se establece en el siguiente nodo en la lista vinculada.

  7. Devuelve falso después del bucle de ruiho porque no se observó un bucle.

  8. Construimos tres objetos de nodo y los inicializamos en la función Main (). Dado que no hay bucle en el primer ejemplo, establecemos los "Siguientes" punteros de cada nodo correctamente.

Conclusión:

En conclusión, el mejor método para detectar bucles en una lista vinculada depende del caso de uso específico y las restricciones del problema. La tabla hash y el algoritmo de búsqueda de ciclo de Floyd son métodos eficientes y se usan ampliamente en la práctica. La pila y la recursión son métodos menos eficientes, pero son más intuitivos.