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

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 le suivant. Supposons qu'il existe une possibilité que la liste contienne une boucle - c'est-à-dire que le nœud final, au lieu d'avoir un null, 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 truesi le nœud donné est le premier d'une liste avec une boucle, et falsesinon? Comment pourriez-vous écrire pour que cela prenne un espace constant et un temps raisonnable?

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

Vous pouvez utiliser l'algorithme de recherche de cycle de Floyd , également connu sous le nom d' algorithme de tortue et de lièvre .

L'idée est d'avoir deux références à la liste et de les déplacer à des vitesses différentes . Avancez un par 1nœud et l'autre par 2nœuds.

• Si la liste chaînée a une boucle, ils se rencontreront certainement .
• Sinon, l'une des deux références (ou la leur next) deviendra null.

Fonction Java implémentant l'algorithme:

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

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
}

Mieux que l'algorithme de Floyd

Richard Brent a décrit un algorithme alternatif de détection de cycle , qui est à peu près comme le lièvre et la tortue [cycle de Floyd] sauf que le nœud lent ici ne bouge pas, mais est plus tard "téléporté" à la position du nœud rapide à fixe intervalles.

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

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

Une solution alternative à la tortue et au lapin, pas tout à fait aussi agréable, car je change temporairement la liste:

L'idée est de parcourir la liste et de l'inverser au fur et à mesure. Ensuite, lorsque vous atteignez pour la première fois un nœud qui a déjà été visité, son prochain pointeur pointera "vers l'arrière", provoquant l'itération à continuer vers firstlà où elle se termine.

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;

Code de test:

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

Tortue et lièvre

Jetez un œil à l'algorithme rho de Pollard . Ce n'est pas tout à fait le même problème, mais peut-être que vous en comprendrez la logique et l'appliquerez aux listes chaînées.

(Si vous êtes paresseux, vous pouvez simplement vérifier la détection de cycle - vérifiez la partie sur la tortue et le lièvre.)

Cela ne nécessite que du temps linéaire et 2 pointeurs supplémentaires.

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 plupart de la solution ne vérifie pas les deux nextet les next.nextvaleurs nulles. De plus, comme la tortue est toujours derrière, vous n'avez pas à la vérifier pour null - le lièvre l'a déjà fait.)

L'utilisateur unicornaddict a un bon algorithme ci-dessus, mais malheureusement il contient un bogue pour les listes non bouclées de longueur impaire> = 3. Le problème est que fastpeut se "bloquer" juste avant la fin de la liste, le slowrattraper, 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;
    }
}

Dans ce contexte, les matériaux textuels sont partout chargés. Je voulais juste publier une représentation schématique qui m'a vraiment aidé à saisir le concept.

Quand rapide et lent se rencontrent au point p,

Distance parcourue par rapide = a + b + c + b = a + 2b + c

Distance parcourue lentement = a + b

Puisque le jeûne est 2 fois plus rapide que le lent. Donc a + 2b + c = 2 (a + b) , alors nous obtenons a = c .

Ainsi, lorsqu'un autre pointeur lent s'exécute à nouveau de la tête à q , en même temps, le pointeur rapide s'exécute de p à q , de sorte qu'ils se rencontrent au point q ensemble.

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

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)

Ce qui suit n'est peut-être pas la meilleure méthode - c'est O (n ^ 2). Cependant, cela devrait servir à faire le travail (éventuellement).

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

Pardonnez-moi mon ignorance (je suis encore relativement nouveau pour Java et la programmation), mais pourquoi cela ne fonctionnerait-il pas?

Je suppose que cela ne résout pas le problème d'espace constant ... mais il y arrive au moins dans un délai raisonnable, n'est-ce pas? Il ne prendra que l'espace de la liste chaînée plus l'espace d'un ensemble avec n éléments (où n est le nombre d'éléments dans la liste chaînée, ou le nombre d'éléments jusqu'à ce qu'il atteigne une boucle). Et pour le temps, l'analyse du pire des cas, je pense, suggérerait O (nlog (n)). Les recherches de SortedSet pour contains () sont log (n) (vérifiez le javadoc, mais je suis sûr que la structure sous-jacente de TreeSet est TreeMap, qui à son tour est un arbre rouge-noir), et dans le pire des cas (pas de boucles, ou boucle à la toute fin), il devra faire n recherches.

Si nous sommes autorisés à intégrer la classe Node, je résoudrais le problème tel que je l'ai implémenté ci-dessous.hasLoop()s'exécute en temps O (n) et ne prend que l'espace de counter. Cela semble-t-il une solution appropriée? Ou existe-t-il un moyen de le faire sans intégration Node? (Évidemment, 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;
        ....
    }

}

Vous pouvez même le faire en temps O (1) constant (bien que ce ne soit pas très rapide ou efficace): il y a une quantité limitée de nœuds que la mémoire de votre ordinateur peut contenir, disons N enregistrements. Si vous parcourez plus de N enregistrements, alors vous avez une boucle.

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

Utilisez la fonction ci-dessus pour détecter une boucle dans une liste liée en Java.

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) à l'aide de hashmap ou O (NlogN) à l'aide d'une approche basée sur le tri.

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

Je ne vois aucun moyen de faire en sorte que cela prenne un temps ou un espace fixe, les deux augmenteront avec la taille de la liste.

Je voudrais utiliser un IdentityHashMap (étant donné qu'il n'y a pas encore d'IdentityHashSet) et stocker chaque nœud dans la carte. Avant qu'un nœud ne soit stocké, vous devez appeler containsKey dessus. Si le nœud existe déjà, vous avez un cycle.

ItentityHashMap utilise == au lieu de .equals afin que vous vérifiiez où l'objet est en mémoire plutôt que s'il a le même contenu.

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

Pourquoi ne peut-on pas stocker l'adresse du nœud et le nœud "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)

Il y a donc un cycle formé.

Voici mon code exécutable.

Ce que j'ai fait est de révérer la liste des liens en utilisant trois nœuds temporaires (complexité de l'espace O(1)) qui gardent une trace des liens.

Le fait intéressant de le faire est d'aider à détecter le cycle dans la liste chaînée, car à mesure que vous avancez, vous ne vous attendez pas à revenir au point de départ (nœud racine) et l'un des nœuds temporaires devrait aller à null, sauf si vous avoir un cycle qui signifie qu'il pointe vers le nœud racine.

La complexité temporelle de cet algorithme est O(n)la complexité spatiale O(1).

Voici le nœud de classe pour la liste chaînée:

public class LinkedNode{
    public LinkedNode next;
}

Voici le code principal avec un cas de test simple de trois nœuds que le dernier nœud pointe vers le deuxième nœud:

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

Voici un cas de test simple de trois nœuds que le dernier nœud pointe vers le deuxième nœud:

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

Ce code est optimisé et produira un résultat plus rapidement qu'avec celui choisi comme meilleure réponse.Ce code évite d'entrer 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 le `` meilleur answer 'method.Look à travers la marche à sec de ce qui suit et vous réaliserez ce que j'essaie de dire.Ensuite, regardez le problème à travers la méthode ci-dessous et mesurez 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
}

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

Vous pouvez également utiliser l'algorithme de tortue de Floyd comme suggéré dans les réponses ci-dessus.

Cet algorithme peut vérifier si une liste liée individuellement a un cycle fermé. Ceci peut être réalisé en itérant une liste avec deux pointeurs qui se déplaceront à une vitesse différente. De cette façon, s'il y a un cycle, les deux pointeurs se rencontreront à un moment donné dans le futur.

N'hésitez pas à consulter mon blog sur la structure de données des listes liées, où j'ai également inclus un extrait de code avec une implémentation de l'algorithme susmentionné en langage java.

Cordialement,

Andreas (@xnorcode)

Voici la solution pour détecter le cycle.

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 
        }

// fonction de boucle de recherche de liste liée

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

Cette approche a une surcharge d'espace, mais une implémentation plus simple:

La boucle peut être identifiée en stockant les nœuds dans une carte. Et avant de mettre le nœud; vérifiez si le nœud existe déjà. Si le nœud existe déjà dans la carte, cela signifie que la liste liée a une boucle.

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;

}