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

Digamos que tiene una estructura de lista vinculada en Java. Se compone de nodos:

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

y cada nodo apunta al siguiente nodo, excepto el último nodo, que tiene un valor nulo para el siguiente. Digamos que existe la posibilidad de que la lista pueda contener un bucle, es decir, el Nodo final, en lugar de tener un valor nulo, tiene una referencia a uno de los nodos en la lista que vino antes.

¿Cuál es la mejor forma de escribir?

boolean hasLoop(Node first)

¿cuál volvería truesi el nodo dado es el primero de una lista con un bucle, y de lo falsecontrario? ¿Cómo podrías escribir para que ocupe una cantidad constante de espacio y una cantidad razonable de tiempo?

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

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 . Mueva uno hacia adelante por 1nodo y el otro por 2nodos.

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

Función Java que implementa 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 Fast / Slow, 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
}

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 en 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 temporal, O (1) complejidad espacial.

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;
}

Una solución alternativa a la tortuga y el conejo, no tan agradable, ya que temporalmente cambio la lista:

La idea es recorrer la lista y revertirla a medida que avanza. Luego, cuando llegue por primera vez a un nodo que ya ha sido visitado, su siguiente puntero apuntará "hacia atrás", haciendo que la iteración avance hacia firstdonde 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);
}

Tortuga y liebre

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

(si eres flojo, puedes verificar la detección del ciclo , verifica 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 comprueban para ambos nexty next.nextpara los nulos Además, dado que la tortuga está siempre detrás, que no tiene que comprobar null -.. La liebre que ya hizo)

El usuario unicornaddict tiene un buen algoritmo anterior, pero desafortunadamente contiene un error para las listas de longitud impar> = 3. El problema es que fastpuede quedar "atascado" justo antes del final de la lista, lo slowalcanza y se detecta (incorrectamente) un bucle.

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;
    }
}

En este contexto, hay cargas de materiales textuales en todas partes. Solo quería publicar una representación esquemática que realmente me ayudó a comprender el concepto.

Cuando rápido y lento se encuentran en el punto p,

Distancia recorrida por rápido = a + b + c + b = a + 2b + c

Distancia recorrida por lento = a + b

Dado que el rápido es 2 veces más rápido que el lento. Entonces a + 2b + c = 2 (a + b) , entonces obtenemos a = c .

Entonces, cuando otro puntero lento vuelve a correr de la cabeza a la q , al mismo tiempo, el puntero rápido corre de p a q , por lo que se encuentran en el punto q juntos.

public ListNode detectCycle(ListNode head) {
    if(head == null || head.next==null)
        return null;

    ListNode slow = head;
    ListNode fast = head;

    while (fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;

        /*
        if the 2 pointers meet, then the 
        dist from the meeting pt to start of loop 
        equals
        dist from head to start of loop
        */
        if (fast == slow){ //loop found
            slow = head;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }            
    }
    return null;
}

Algoritmo

public static boolean hasCycle (LinkedList<Node> list)
{
    HashSet<Node> visited = new HashSet<Node>();

    for (Node n : list)
    {
        visited.add(n);

        if (visited.contains(n.next))
        {
            return true;
        }
    }

    return false;
}

Complejidad

Time ~ O(n)
Space ~ O(n)

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 <count_of_elements_so_far>
    if found, then you have a loop
    else,count_of_elements_so_far++;
}

public boolean hasLoop(Node start){   
   TreeSet<Node> set = new TreeSet<Node>();
   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óname mi ignorancia (todavía soy bastante nuevo en Java y programación), pero ¿por qué no funcionaría lo anterior?

Supongo que esto no resuelve el problema del espacio constante ... pero al menos llega allí 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 vinculada, o el número de elementos hasta que llegue a un bucle). Y por el momento, el análisis del peor de los casos, creo, sugeriría O (nlog (n)). Las búsquedas de SortedSet para contienen () son log (n) (verifique el javadoc, pero estoy bastante 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 bucle al final), tendrá que hacer n búsquedas.

Si se nos permite incrustar la clase Node, resolvería el problema tal como lo he implementado a continuación. hasLoop()se ejecuta en O (n) tiempo y solo ocupa el espacio de counter. ¿Parece esto una solución adecuada? ¿O hay una manera 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 un 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 atraviesa 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;
        }
    }
}

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;
}

Utilice la función anterior para detectar un bucle en la lista vinculada 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 la complejidad de O (N) usando hashmap u O (NlogN) usando un enfoque basado en la ordenación.

A medida que recorre la lista 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 requiere complejidad O (logN).

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

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

ItentityHashMap usa == en lugar de .equals para que esté verificando dónde está el objeto en la memoria en lugar de si tiene el mismo contenido.

Podría llegar terriblemente tarde y nuevo para manejar este hilo. Pero aún..

¿Por qué no se puede almacenar la dirección del nodo y el nodo "siguiente" señalado 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, se forma un ciclo.

Aquí está mi código ejecutable.

Lo que he hecho es reverenciar la lista vinculada mediante el uso de tres nodos temporales (complejidad del espacio O(1)) que realizan 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 ir a nulo a menos que usted tener un ciclo que significa que apunta al nodo raíz.

La complejidad temporal de este algoritmo es O(n)y la complejidad espacial es O(1).

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

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 elegido como la mejor respuesta. Este código evita entrar en un proceso muy largo de perseguir el puntero de nodo hacia adelante y hacia atrás que ocurrirá en el siguiente caso si seguimos el 'mejor 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 método dado a continuación y mida el no. de pasos dados 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
}

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;
}

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 individualmente tiene un ciclo cerrado. Esto se puede lograr iterando una lista con dos punteros que se moverán a una velocidad diferente. De esta manera, si hay un ciclo, los dos punteros se encontrarán en algún momento en el futuro.

Por favor, siéntase libre de revisar mi blog en la estructura de datos de las listas vinculadas, 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 
        }

// función de bucle de búsqueda de lista vinculada

int findLoop(struct Node* head)
{
    struct Node* slow = head, *fast = head;
    while(slow && fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return 1;
    }
 return 0;
}

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

El bucle se puede identificar almacenando nodos en un mapa. Y antes de poner el nodo; compruebe si el nodo ya existe. Si el nodo ya existe en el mapa, significa que la Lista vinculada tiene un bucle.

public boolean loopDetector(Node<E> first) {  
       Node<E> t = first;  
       Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();  
       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;  
  }  

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;

}