¿Qué es un algoritmo eficiente para encontrar si una lista vinculada individualmente es circular / cíclica o no?

¿Cómo puedo saber si una lista enlazada individualmente es circular / cíclica o no? Traté de buscar pero no pude encontrar una solución satisfactoria. Si es posible, ¿puede proporcionar un pseudocódigo o una implementación de Java?

Por ejemplo:
135714575 , donde el segundo 5 es realmente el tercer elemento de la lista.

La respuesta estándar es tomar dos iteradores al principio, incrementar el primero una vez y el segundo dos veces. Verifique si apuntan al mismo objeto. Luego, repita hasta que el que está aumentando dos veces llegue al primero o llegue al final.

Este algoritmo encuentra cualquier enlace circular en la lista, no solo que es un círculo completo.

Pseudo-código (no Java, no probado, fuera de mi cabeza)

 bool hasCircle(List l) { Iterator i = l.begin(), j = l.begin(); while (true) { // increment the iterators, if either is at the end, you're done, no circle if (i.hasNext()) i = i.next(); else return false; // second iterator is travelling twice as fast as first if (j.hasNext()) j = j.next(); else return false; if (j.hasNext()) j = j.next(); else return false; // this should be whatever test shows that the two // iterators are pointing at the same place if (i.getObject() == j.getObject()) { return true; } } } 

Un algoritmo simple llamado algoritmo de Floyd es tener dos punteros, ayb, que comienzan en el primer elemento de la lista enlazada. Luego, en cada paso, incrementa una vez yb dos veces. Repita hasta que llegue al final de la lista (sin bucle), o a == b (la lista enlazada contiene un bucle).

Otro algoritmo es el algoritmo de Brent .

Tres estrategias principales que conozco:

  1. Comienza a recorrer la lista y realiza un seguimiento de todos los nodos que has visitado (por ejemplo, almacena sus direcciones en un mapa). Cada nuevo nodo que visite, verifique si ya lo ha visitado. Si ya ha visitado el nodo, obviamente hay un bucle. Si no hay un bucle, llegarás al final con el tiempo. Esto no es genial porque es O (N) la complejidad del espacio para almacenar la información adicional.

  2. La solución Tortoise / Hare. Iniciar dos punteros en la parte delantera de la lista. El primer puntero, la “tortuga” avanza un nodo en cada iteración. El otro puntero, la “liebre” avanza dos nodos en cada iteración. Si no hay ningún bucle, la liebre y la tortuga llegarán al final de la lista. Si hay un bucle, la liebre pasará a la tortuga en algún momento y cuando eso suceda, sabrás que hay un bucle. Esta es O (1) complejidad espacial y un algoritmo bastante simple.

  3. Usa el algoritmo para invertir una lista enlazada. Si la lista tiene un bucle, terminará al principio de la lista al intentar revertirla. Si no tiene un bucle, terminarás de revertirlo y llegarás al final. Esto es O (1) complejidad de espacio, pero un algoritmo ligeramente más feo.

Conté tus nodos y llego a * la cabeza otra vez.

¿Qué hay de siguiente enfoque:

Ordene la lista de enlaces en orden ascendente siguiendo cualquier algoritmo estándar. Antes de ordenar: 4-2-6-1-5 After Sort: 1-2-4-5-6

Una vez clasificados, verifique los datos de cada nodo y compárelos con los datos del nodo del enlace, algo como esto:

if (currentcode-> data> currentnode-> link-> data) es decir, circular = verdadero;

En cualquier comparación, si alguno de “currentnode-> data” es mayor que “currentcode-> link-> data” para una lista de enlaces ordenada, significa que el nodo actual apunta a un nodo anterior (es decir, circular);

Chicos, no tengo la configuración para probar el código. Déjeme ahora si este concepto funciona.

Usa el algoritmo Tortoise-Hare .

@samoz tiene en mi punto de vista la respuesta! Pseudo código faltante Seria algo asi

tu lista es tu lista enlazada

 allnodes = hashmap while yourlist.hasNext() node = yourlist.next() if(allnodes.contains(node)) syso "loop found" break; hashmap.add(node) 

lo siento, el código es muy pseudo (haga más scripting que java últimamente)

Comience en un nodo y regístrelo, luego repita la iteración en toda la lista hasta que llegue a un puntero nulo o al nodo con el que comenzó.

Algo como:

 Node start = list->head; Node temp = start->next; bool circular = false; while(temp != null && temp != start) { if(temp == start) { circular = true; break; } temp = temp->next; } return circular 

Esto es O (n), que es lo mejor que puedes obtener con una lista enlazada individualmente (corrígeme si me equivoco).

O para encontrar cualquier ciclo en la lista (como el medio), puedes hacer:

 Node[] array; // Use a vector or ArrayList to support dynamic insertions Node temp = list->head; bool circular = false; while(temp != null) { if(array.contains(temp) == true) { circular = true; break; } array.insert(temp); temp = temp->next; } return circular 

Esto será un poco más lento debido a los tiempos de inserción de las matrices dinámicas.

Aquí hay un buen sitio en el que se pueden copiar las diferentes soluciones.

encontrar bucle lista enlazada individualmente

Este es el ganador en ese sitio

 // Best solution function boolean hasLoop(Node startNode){ Node slowNode = Node fastNode1 = Node fastNode2 = startNode; while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){ if (slowNode == fastNode1 || slowNode == fastNode2) return true; slowNode = slowNode.next(); } return false; } 

Esta solución es el “Algoritmo de búsqueda de ciclos de Floyd” publicado en “Algoritmos no deterministas” por Robert W. Floyd en 1967. También se lo conoce como “Algoritmo de la liebre y la tortuga”.

Un algoritmo es:

  1. Almacenar el puntero al primer nodo.
  2. Recorre la lista comparando cada puntero de nodo con este puntero
  3. Si encuentra un puntero NULL, entonces su lista no está unida circularmente
  4. Si se encuentra con el primer nodo mientras se cruza, entonces se trata de una lista con enlaces circulares

Nunca terminará del bucle, también se puede hacer en la siguiente solución:

 bool hasCircle(List l) { Iterator i = l.begin(), j = l.begin(); while (true) { // increment the iterators, if either is at the end, you're done, no circle if (i.hasNext()) i = i.next(); else return false; // second iterator is travelling twice as fast as first if (j.hasNext()) j = j.next(); else return false; if (j.hasNext()) j = j.next(); else return false; // this should be whatever test shows that the two // iterators are pointing at the same place if (i.getObject() == j.getObject()) { return true; } if(i.next()==j) break; } } 

Prueba esto

 /* Link list Node */ 

struct Node {int data; struct Node * next; };

/ * Esta función devuelve verdadero si la lista enlazada es circular, de lo contrario es falsa. * / bool isCircular (struct Node * head) {// Una lista enlazada vacía es circular si (head == NULL) devuelve true;

 // Next of head struct Node *node = head->next; // This loop would stope in both cases (1) If // Circular (2) Not circular while (node != NULL && node != head) node = node->next; // If loop stopped because of circular // condition return (node == head); 

}