[java] Comment détecter une boucle dans une liste chaînée?



Answers

Voici un raffinement de la solution Fast / Slow, qui gère correctement les listes de longueurs impaires et améliore la clarté.

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

Supposons que vous ayez une structure de liste liée en Java. Il est composé de nœuds:

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

et chaque nœud pointe vers le nœud suivant, à l'exception du dernier nœud, qui a la valeur null pour la suivante. Supposons qu'il existe une possibilité que la liste puisse contenir une boucle - c'est-à-dire que le nœud final, au lieu d'avoir une valeur nulle, a une référence à l'un des nœuds de la liste qui l'a précédé.

Quelle est la meilleure façon d'écrire

boolean hasLoop(Node first)

qui retournerait true si le Node donné est le premier d'une liste avec une boucle, et false sinon? Comment pourriez-vous écrire pour que cela prenne une quantité constante d'espace et un temps raisonnable?

Voici une image de ce à quoi ressemble une liste avec une boucle:




La détection d'une boucle dans une liste chaînée peut être effectuée de l'une des manières les plus simples, ce qui entraîne une complexité O (N).

Lorsque vous parcourez la liste en commençant par la tête, créez une liste d'adresses triées. Lorsque vous insérez une nouvelle adresse, vérifiez si l'adresse est déjà présente dans la liste triée, ce qui prend en compte la complexité de O (logN).




Algorithme

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

Complexité

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



Si nous sommes autorisés à intégrer le Node classe, je résoudrais le problème comme je l'ai implémenté ci-dessous. hasLoop() s'exécute en O (n) time, et ne prend que l'espace du counter . Est-ce que cela semble être une solution appropriée? Ou y a-t-il un moyen de le faire sans intégrer Node ? (Evidemment, dans une implémentation réelle il y aurait plus de méthodes, comme 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;
        ....
    }

}



Ce code est optimisé et produira un résultat plus rapide qu'avec celui choisi comme la meilleure réponse. Ce code évite d'aller dans un très long processus de poursuite du pointeur de nœud avant et arrière qui se produira dans le cas suivant si nous suivons les méthode de réponse.Look à travers la course à sec de ce qui suit et vous réaliserez ce que je suis en train de dire.Puis regardez le problème à travers la méthode donnée ci-dessous et de mesurer le non. des mesures prises pour trouver la réponse.

1-> 2-> 9-> 3 ^ -------- ^

Voici le code:

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
}



L'utilisateur unicornaddict a un bon algorithme ci-dessus, mais malheureusement il contient un bug pour les listes non-loopy de longueur impair> = 3. Le problème est que fast peut être "coincé" juste avant la fin de la liste, rattrape slow , et une boucle est (à tort) détectée.

Voici l'algorithme corrigé.

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



Mieux que l'algorithme de Floyd

Richard Brent a décrit un algorithme de détection de cycle alternatif , qui ressemble beaucoup au lièvre et à la tortue [cycle de Floyd], sauf que le nœud lent ne bouge pas, mais est ensuite "téléporté" à la position du nœud rapide à intervalles.

La description est disponible ici: http://www.siafoo.net/algorithm/11 Brent prétend que son algorithme est de 24 à 36% plus rapide que l'algorithme du cycle de Floyd. O (n) complexité du temps, O (1) complexité de l'espace.

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



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;

}



Voici ma solution 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;
}



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



Je pourrais être terriblement en retard et nouveau pour gérer ce fil. Mais reste..

Pourquoi ne peut pas stocker l'adresse du noeud et le noeud "suivant" pointé dans une table

Si nous pouvions tabuler de cette façon

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)

D'où il y a un cycle formé.




Related