¿Cómo detectar un bucle en una lista vinculada?

Supongamos que tiene una estructura de listas enlazadas en Java. Está compuesto de Nodos:

class Node { Node next; // some user data } 

y cada nodo apunta al siguiente nodo, a excepción del último nodo, que tiene nulo para el siguiente. Supongamos que existe la posibilidad de que la lista contenga un bucle, es decir, el nodo final, en lugar de tener un valor nulo, tiene una referencia a uno de los nodos de la lista que le precedió.

Cuál es la mejor manera de escribir

 boolean hasLoop(Node first) 

que devolvería true si el Nodo dado es el primero de una lista con un bucle, y de lo contrario es false ? ¿Cómo podría escribir para que ocupe una cantidad constante de espacio y una cantidad de tiempo razonable?

Aquí hay una imagen de cómo se ve una lista con un bucle:

texto alternativo

Puede utilizar el algoritmo de búsqueda de ciclos de Floyd , también conocido como algoritmo de tortuga y liebre .

La idea es tener dos referencias a la lista y moverlas a diferentes velocidades . Mueve uno adelante por 1 nodo y el otro por 2 nodos.

  • Si la lista enlazada tiene un bucle, definitivamente se encontrarán.
  • De lo contrario, cualquiera de las dos referencias (o la next ) se convertirá en null .

Función Java implementando el algoritmo:

 boolean hasLoop(Node first) { if(first == null) // list does not exist..so no loop either return false; Node slow, fast; // create two references. slow = fast = first; // make both refer to the start of the list while(true) { slow = slow.next; // 1 hop if(fast.next != null) fast = fast.next.next; // 2 hops else return false; // next node null => no loop if(slow == null || fast == null) // if either hits null..no loop return false; if(slow == fast) // if the two ever meet...we must have a loop return true; } } 

Aquí hay un refinamiento de la solución Rápida / Lenta, que maneja correctamente las listas de longitud impar y mejora la claridad.

 boolean hasLoop(Node first) { Node slow = first; Node fast = first; while(fast != null && fast.next != null) { slow = slow.next; // 1 hop fast = fast.next.next; // 2 hops if(slow == fast) // fast caught up to slow, so there is a loop return true; } return false; // fast reached null, so the list terminates } 

Una solución alternativa para Turtle and Rabbit, no tan bonita, ya que cambio temporalmente la lista:

La idea es recorrer la lista e invertirla sobre la marcha. Luego, cuando llegue por primera vez a un nodo que ya ha sido visitado, su próximo puntero apuntará “hacia atrás”, haciendo que la iteración avance hacia la first , donde termina.

 Node prev = null; Node cur = first; while (cur != null) { Node next = cur.next; cur.next = prev; prev = cur; cur = next; } boolean hasCycle = prev == first && first != null && first.next != null; // reconstruct the list cur = prev; prev = null; while (cur != null) { Node next = cur.next; cur.next = prev; prev = cur; cur = next; } return hasCycle; 

Código de prueba:

 static void assertSameOrder(Node[] nodes) { for (int i = 0; i < nodes.length - 1; i++) { assert nodes[i].next == nodes[i + 1]; } } public static void main(String[] args) { Node[] nodes = new Node[100]; for (int i = 0; i < nodes.length; i++) { nodes[i] = new Node(); } for (int i = 0; i < nodes.length - 1; i++) { nodes[i].next = nodes[i + 1]; } Node first = nodes[0]; Node max = nodes[nodes.length - 1]; max.next = null; assert !hasCycle(first); assertSameOrder(nodes); max.next = first; assert hasCycle(first); assertSameOrder(nodes); max.next = max; assert hasCycle(first); assertSameOrder(nodes); max.next = nodes[50]; assert hasCycle(first); assertSameOrder(nodes); } 

Mejor que el algoritmo de Floyd

Richard Brent describió un algoritmo de detección de ciclo alternativo , que es muy parecido a la liebre y la tortuga [ciclo de Floyd] excepto que, el nodo lento aquí no se mueve, pero luego es “teletransportado” a la posición del nodo rápido a nivel fijo intervalos.

La descripción está disponible aquí: http://www.siafoo.net/algorithm/11 Brent afirma que su algoritmo es 24 a 36% más rápido que el algoritmo de ciclo de Floyd. O (n) complejidad del tiempo, O (1) complejidad del espacio.

 public static boolean hasLoop(Node root){ if(root == null) return false; Node slow = root, fast = root; int taken = 0, limit = 2; while (fast.next != null) { fast = fast.next; taken++; if(slow == fast) return true; if(taken == limit){ taken = 0; limit <<= 1; // equivalent to limit *= 2; slow = fast; // teleporting the turtle (to the hare's position) } } return false; } 

Tortuga y liebre

Echa un vistazo al algoritmo rho de Pollard . No es exactamente el mismo problema, pero tal vez comprenderá la lógica y lo aplicará a listas vinculadas.

(Si eres perezoso, simplemente puedes verificar la detección de ciclos ; revisa la parte sobre la tortuga y la liebre).

Esto solo requiere tiempo lineal y 2 punteros adicionales.

En Java:

 boolean hasLoop( Node first ) { if ( first == null ) return false; Node turtle = first; Node hare = first; while ( hare.next != null && hare.next.next != null ) { turtle = turtle.next; hare = hare.next.next; if ( turtle == hare ) return true; } return false; } 

(La mayor parte de la solución no verifica tanto el next como el next next.next Para next.next . Además, dado que la tortuga siempre está detrás, no es necesario que la verifique como nula, la liebre ya lo hizo).

El usuario unicornaddict tiene un buen algoritmo arriba, pero desafortunadamente contiene un error para listas no bucles de longitud impar> = 3. El problema es que fast puede quedar “atorado” justo antes del final de la lista, slow alcanza , y un bucle es (erróneamente) detectado.

Aquí está el algoritmo corregido.

 static boolean hasLoop(Node first) { if(first == null) // list does not exist..so no loop either. return false; Node slow, fast; // create two references. slow = fast = first; // make both refer to the start of the list. while(true) { slow = slow.next; // 1 hop. if(fast.next == null) fast = null; else fast = fast.next.next; // 2 hops. if(fast == null) // if fast hits null..no loop. return false; if(slow == fast) // if the two ever meet...we must have a loop. return true; } } 

El siguiente puede no ser el mejor método: es O (n ^ 2). Sin embargo, debería servir para hacer el trabajo (eventualmente).

 count_of_elements_so_far = 0; for (each element in linked list) { search for current element in first  if found, then you have a loop else,count_of_elements_so_far++; } 

Algoritmo

 public static boolean hasCycle (LinkedList list) { HashSet visited = new HashSet(); for (Node n : list) { visited.add(n); if (visited.contains(n.next)) { return true; } } return false; } 

Complejidad

 Time ~ O(n) Space ~ O(n) 
 public boolean hasLoop(Node start){ TreeSet set = new TreeSet(); Node lookingAt = start; while (lookingAt.peek() != null){ lookingAt = lookingAt.next; if (set.contains(lookingAt){ return false; } else { set.put(lookingAt); } return true; } // Inside our Node class: public Node peek(){ return this.next; } 

Perdóneme mi ignorancia (todavía soy bastante nuevo en Java y progtwigción), pero ¿por qué no funcionaría lo anterior?

Supongo que esto no resuelve el problema del espacio constante … pero al menos llega en un tiempo razonable, ¿correcto? Solo ocupará el espacio de la lista vinculada más el espacio de un conjunto con n elementos (donde n es el número de elementos en la lista enlazada, o el número de elementos hasta que alcanza un bucle). Y por el momento, el peor de los casos, creo, sugeriría O (nlog (n)). Las búsquedas de SortedSet para contains () son log (n) (compruebe javadoc, pero estoy seguro de que la estructura subyacente de TreeSet es TreeMap, que a su vez es un árbol rojo-negro), y en el peor de los casos (sin bucles, o loop al final), tendrá que hacer n búsquedas.

Si podemos incrustar el Node la clase, resolvería el problema como lo he implementado a continuación. hasLoop() ejecuta en el tiempo O (n) y toma solo el espacio del counter . ¿Esto parece una solución apropiada? ¿O hay una forma de hacerlo sin incrustar Node ? (Obviamente, en una implementación real habría más métodos, como RemoveNode(Node n) , etc.)

 public class LinkedNodeList { Node first; Int count; LinkedNodeList(){ first = null; count = 0; } LinkedNodeList(Node n){ if (n.next != null){ throw new error("must start with single node!"); } else { first = n; count = 1; } } public void addNode(Node n){ Node lookingAt = first; while(lookingAt.next != null){ lookingAt = lookingAt.next; } lookingAt.next = n; count++; } public boolean hasLoop(){ int counter = 0; Node lookingAt = first; while(lookingAt.next != null){ counter++; if (count < counter){ return false; } else { lookingAt = lookingAt.next; } } return true; } private class Node{ Node next; .... } } 

Incluso podría hacerlo en tiempo O (1) constante (aunque no sería muy rápido o eficiente): hay una cantidad limitada de nodos que la memoria de su computadora puede contener, digamos N registros. Si recorre más de N registros, entonces tiene un bucle.

  // To detect whether a circular loop exists in a linked list public boolean findCircularLoop() { Node slower, faster; slower = head; faster = head.next; // start faster one node ahead while (true) { // if the faster pointer encounters a NULL element if (faster == null || faster.next == null) return false; // if faster pointer ever equals slower or faster's next // pointer is ever equal to slower then it's a circular list else if (slower == faster || slower == faster.next) return true; else { // advance the pointers slower = slower.next; faster = faster.next.next; } } } 

No veo ninguna manera de hacer que esto tome una cantidad fija de tiempo o espacio, ambos boostán con el tamaño de la lista.

Haría uso de un IdentityHashMap (dado que aún no hay un IdentityHashSet) y almacenaré cada Nodo en el mapa. Antes de que se almacene un nodo, debe llamar a containsKey en él. Si el Nodo ya existe tienes un ciclo.

ItentityHashMap utiliza == en lugar de .equals para que pueda verificar dónde está el objeto en la memoria en lugar de si tiene el mismo contenido.

Podría ser terriblemente tarde y nueva para manejar este hilo. Pero aún..

¿Por qué no se puede almacenar la dirección del nodo y el “próximo” nodo en una tabla?

Si pudiéramos tabular de esta manera

 node present: (present node addr) (next node address) node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200) node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300) node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400) node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500) node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600) node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400) 

Por lo tanto, hay un ciclo formado.

Aquí está mi código ejecutable.

Lo que he hecho es reverenciar la lista enlazada utilizando tres nodos temporales (complejidad de espacio O(1) ) que mantienen un seguimiento de los enlaces.

El hecho interesante de hacerlo es ayudar a detectar el ciclo en la lista vinculada porque a medida que avanza, no espera volver al punto de partida (nodo raíz) y uno de los nodos temporales debería pasar a nulo a menos que tiene un ciclo que significa que apunta al nodo raíz.

La complejidad de tiempo de este algoritmo es O(n) y la complejidad del espacio es O(1) .

Aquí está el nodo de clase para la lista enlazada:

 public class LinkedNode{ public LinkedNode next; } 

Aquí está el código principal con un caso de prueba simple de tres nodos que el último nodo apunta al segundo nodo:

  public static boolean checkLoopInLinkedList(LinkedNode root){ if (root == null || root.next == null) return false; LinkedNode current1 = root, current2 = root.next, current3 = root.next.next; root.next = null; current2.next = current1; while(current3 != null){ if(current3 == root) return true; current1 = current2; current2 = current3; current3 = current3.next; current2.next = current1; } return false; } 

Aquí está el caso de prueba simple de tres nodos que el último nodo apunta al segundo nodo:

 public class questions{ public static void main(String [] args){ LinkedNode n1 = new LinkedNode(); LinkedNode n2 = new LinkedNode(); LinkedNode n3 = new LinkedNode(); n1.next = n2; n2.next = n3; n3.next = n2; System.out.print(checkLoopInLinkedList(n1)); } } 

Este código está optimizado y producirá un resultado más rápido que con el que se eligió como la mejor respuesta. Este código evita entrar en un proceso muy largo de búsqueda del puntero de nodo hacia adelante y hacia atrás que ocurrirá en el siguiente caso si seguimos el ‘mejor Método de respuesta. Mire a través de la ejecución en seco de lo siguiente y se dará cuenta de lo que estoy tratando de decir. Luego mire el problema a través del siguiente método y mida el no. de pasos tomados para encontrar la respuesta.

1-> 2-> 9-> 3 ^ ——– ^

Aquí está el código:

 boolean loop(node *head) { node *back=head; node *front=head; while(front && front->next) { front=front->next->next; if(back==front) return true; else back=back->next; } return false } 
 boolean hasCycle(Node head) { boolean dec = false; Node first = head; Node sec = head; while(first != null && sec != null) { first = first.next; sec = sec.next.next; if(first == sec ) { dec = true; break; } } return dec; } 

Use la función anterior para detectar un bucle en la lista de enlaces en java.

La detección de un bucle en una lista vinculada se puede hacer de una de las formas más simples, lo que resulta en una complejidad O (N).

A medida que recorre la lista comenzando desde la cabecera, cree una lista ordenada de direcciones. Cuando inserte una nueva dirección, verifique si la dirección ya está allí en la lista ordenada, lo que toma la complejidad O (logN).

También puede usar el algoritmo de tortuga de Floyd como se sugiere en las respuestas anteriores.

Este algoritmo puede verificar si una lista vinculada solo tiene un ciclo cerrado. Esto se puede lograr iterando una lista con dos punteros que se moverán a diferentes velocidades. De esta forma, si hay un ciclo, los dos indicadores se encontrarán en algún momento en el futuro.

Por favor, siéntase libre de revisar mi publicación de blog en la estructura de datos de las listas enlazadas, donde también incluí un fragmento de código con una implementación del algoritmo mencionado anteriormente en lenguaje Java.

Saludos,

Andreas (@xnorcode)

Aquí está la solución para detectar el ciclo.

 public boolean hasCycle(ListNode head) { ListNode slow =head; ListNode fast =head; while(fast!=null && fast.next!=null){ slow = slow.next; // slow pointer only one hop fast = fast.next.next; // fast pointer two hops if(slow == fast) return true; // retrun true if fast meet slow pointer } return false; // return false if fast pointer stop at end } 

Este enfoque tiene una sobrecarga de espacio, pero una implementación más simple:

El bucle puede identificarse almacenando nodos en un Mapa. Y antes de poner el nodo; verificar si el nodo ya existe Si el nodo ya existe en el mapa, significa que Linked List tiene un bucle.

 public boolean loopDetector(Node first) { Node t = first; Map, Node> map = new IdentityHashMap, Node>(); while (t != null) { if (map.containsKey(t)) { System.out.println(" duplicate Node is --" + t + " having value :" + t.data); return true; } else { map.put(t, t); } t = t.next; } return false; } 

Aquí está mi solución en java

 boolean detectLoop(Node head){ Node fastRunner = head; Node slowRunner = head; while(fastRunner != null && slowRunner !=null && fastRunner.next != null){ fastRunner = fastRunner.next.next; slowRunner = slowRunner.next; if(fastRunner == slowRunner){ return true; } } return false; } 
 public boolean isCircular() { if (head == null) return false; Node temp1 = head; Node temp2 = head; try { while (temp2.next != null) { temp2 = temp2.next.next.next; temp1 = temp1.next; if (temp1 == temp2 || temp1 == temp2.next) return true; } } catch (NullPointerException ex) { return false; } return false; }