Trouver en boucle dans une seule liste liée

Vous pouvez détecter simplement en exécutant deux pointeurs par le biais de la liste, ce processus est connu comme la tortue et le lièvre algorithme d'après la fable du même nom.

Tout d'abord, vérifiez si la liste est vide (head est null). Si oui, aucune boucle n'est possible afin d'arrêter maintenant.

Sinon, le début de la première pointeur tortoise sur le premier nœud head, et le deuxième pointeur hare sur le second nœud head.next.

Puis une boucle continue jusqu'à ce que hare est null (qui peut être déjà le cas dans un élément de liste), l'avancement de tortoise par un et hare par deux à chaque itération. Le lièvre est garanti d'atteindre la fin de la première (si il y est fin) depuis qu'il a commencé à l'avance et s'exécute plus rapidement.

Si il n'y a pas de fin (c'est à dire, si il y a une boucle), il finira par pointer vers le même nœud et vous pouvez vous arrêter, en sachant que vous avez trouvé un nœud quelque part à l'intérieur de la boucle.

Envisager la boucle suivante, qui commence à 3:

head -> 1 -> 2 -> 3 -> 4 -> 5
                  ^         |
                  |         V
                  8 <- 7 <- 6

De départ tortoise à 1 et hare à 2, ils prennent les valeurs suivantes:

(tortoise,hare) = (1,2) (2,4) (3,6) (4,8) (5,4) (6,6)

Parce qu'ils deviennent égaux à (6,6), et depuis hare devrait toujours être au-delà de tortoise dans un non-bouclage de la liste, cela signifie que vous avez découvert une boucle.

Le pseudo-code d'aller quelque chose comme ceci:

def hasLoop (head):
  return false if head = null           # Empty list has no loop.

  tortoise = head                       # tortoise initially first element.
  hare = tortoise.next                  # Set hare to second element.

  while hare != null:                   # Go until hare reaches end.
    return false if hare.next null      # Check enough left for hare move.
    hare = hare.next.next               # Move hare forward two.

    tortoise = tortoise.next            # Move tortoise forward one.

    return true if hare = tortoise      # Same means loop found.
  endwhile

  return false                          # Loop exit means no loop.
enddef

Le temps de la complexité de cet algorithme est O(n) puisque le nombre de nœuds visités (par tortue et le lièvre) est proportionnelle au nombre de nœuds.

---

Une fois que vous savez un nœud dans la boucle, il y a aussi un O(n) méthode garantie pour trouver le commencer de la boucle.

Nous allons revenir à la position initiale après que vous avez trouvé un élément quelque part dans la boucle, mais vous ne savez pas où le début de la boucle.

head -> 1 -> 2 -> 3 -> 4 -> 5
                  ^         |
                  |         V
                  8 <- 7 <- 6
                             \
                              x (where hare and tortoise met).

C'est le processus à suivre:

• Avance hare et définir size à 1.
• Puis, tant qu' hare et tortoise sont différents, continuer à avancer hare, l'augmentation de size à chaque fois. Ce terme donne la taille de la boucle, six dans ce cas.
• À ce point, si size est 1, cela signifie que you must *already* be at the start of the loop (in a loop of size one, there is only one possible node that can *be* in the loop so it *must* be the first in that loop). In this case, you simply returnlièvre " que le début, et passer le reste de la procédure ci-dessous.
• Sinon, réglez les deux hare et tortoise à la première élément de la liste et de faire progresser hare exactement size fois (à la 7 dans ce cas). Cela donne deux pointeurs qui sont différents par exactement la taille de la boucle.
• Puis, tant qu' hare et tortoise sont différents, les faire progresser ensemble (avec le lièvre à courir à un rythme plus calme, la même vitesse que la tortue - je suppose qu'il est fatigué de son premier run). Depuis, ils resteront exactement size éléments les uns des autres en tout temps, tortoise sera atteindre le début de la boucle, à l' exactement même temps que hare retourne le début de la boucle.

Vous pouvez le voir avec la suite de la soluce:

size  tortoise  hare  comment
----  --------  ----  -------
   6         1     1  initial state
                   7  advance hare by six
             2     8  1/7 different, so advance both together
             3     3  2/8 different, so advance both together
                      3/3 same, so exit loop

Donc 3 est le point de départ de la boucle, et depuis ces deux opérations (la détection de boucle et le début de la boucle de découverte) sont O(n) et réalisées de façon séquentielle, le tout pris dans leur ensemble est également O(n).

---

Si vous voulez une preuve formelle que cela fonctionne, vous pouvez consulter les ressources suivantes:

• un question sur notre site de soeur;
• la Wikipédia cycle de détection page; ou
• "La Tortue et le Lièvre Algorithme" par Peter Gammie, le 17 avril 2016.

Si vous êtes tout simplement après l'appui de la méthode (pas de preuve formelle), vous pouvez exécuter les opérations suivantes à Python 3 programme qui évalue sa maniabilité pour un grand nombre de tailles (nombre d'éléments dans le cycle) et de plomb-ins (éléments avant le début du cycle).

Vous verrez qu'il trouve toujours un point où les deux pointeurs de répondre:

def nextp(p, ld, sz):
    if p == ld + sz:
        return ld
    return p + 1

for size in range(1,1001):
    for lead in range(1001):
        p1 = 0
        p2 = 0
        while True:
            p1 = nextp(p1, lead, size)
            p2 = nextp(nextp(p2, lead, size), lead, size)
            if p1 == p2:
                print("sz = %d, ld = %d, found = %d" % (size, lead, p1))
                break

Vous pouvez utiliser hachage carte pour trouver si un lien de la liste ont en boucle ou non ci-dessous utilise la fonction de hachage de la carte pour savoir si le lien de la liste ont en boucle ou pas

    static bool isListHaveALoopUsingHashMap(Link *headLink) {

        map<Link*, int> tempMap;
        Link * temp;
        temp = headLink;
        while (temp->next != NULL) {
            if (tempMap.find(temp) == tempMap.end()) {
                tempMap[temp] = 1;
            } else {
                return 0;
            }
            temp = temp->next;
        }
        return 1;
    }

Deux pointeur de la méthode est la meilleure approche, car le temps de la complexité est O(n) Hachage Carte requise plus O(n) l'espace de la complexité.

Pour la plupart, toutes les réponses précédentes sont correctes, mais voici une version simplifiée de la logique avec visual & code (pour Python 3.7)

La logique est très simple, comme les autres, il a expliqué. Je vais créer Tortue/lent et le Lièvre rapide. Si nous passons deux pointeurs avec une vitesse différente, alors finalement rapide permettra de répondre à la lente !! vous pouvez aussi penser à ce que les deux coureurs dans un virement de bord circulaire de terrain. Si le fast runner continue à aller dans cercle puis il va rencontrer/passer le slow runner.

Donc, nous allons aller de l'Tortue/lent pointeur avec la vitesse de 1 à chaque itération, tandis que nous observons l'incrémentation ou de déplacer le Lièvre rapide/pointeur avec une vitesse de 2. Lorsqu'ils se rencontrent, nous savons qu'il existe un cycle. Ceci est également connu comme Floyd algorithme de recherche des cycles

Voici le code Python qui est-ce (avis has_cycle méthode est la partie principale):

#!/usr/bin/env python3
class Node:
    def __init__(self, data = None):
        self.data = data
        self.next = None
    def strnode (self):
        print(self.data)


class LinkedList:
    def __init__(self):
        self.numnodes = 0
        self.head = None


    def insertLast(self, data):
        newnode = Node(data)
        newnode.next = None
        if self.head == None:
            self.head = newnode
            return

        lnode = self.head
        while lnode.next != None :
            lnode = lnode.next
        lnode.next = newnode # new node is now the last node
        self.numnodes += 1

    def has_cycle(self):    
        slow, fast = self.head ,self.head  
        while fast != None:       
            if fast.next != None:
                 fast = fast.next.next
            else:
                 return False
            slow = slow.next  
            if slow == fast:
                print("--slow",slow.data, "fast",fast.data) 
                return True    
        return False


linkedList = LinkedList()
linkedList.insertLast("1")
linkedList.insertLast("2")
linkedList.insertLast("3")


# Create a loop for testing 
linkedList.head.next.next.next = linkedList.head; 
#let's check and see !
print(linkedList.has_cycle())

boolean hasLoop(Node *head)
    {
      Node *current = head;
      Node *check = null;
      int firstPtr = 0;
      int secondPtr = 2;
      do {
        if (check == current) return true;
        if (firstPtr >= secondPtr){
            check = current;
            firstPtr = 0;
            secondPtr= 2*secondPtr;
        }
        firstPtr ++;
      } while (current = current->next());
      return false;
    }

Un autre O(n) solution.

ok - j'ai couru dans une interview hier - pas de matériaux de référence disponibles et je suis venu avec un de très différent de la réponse (tout en conduisant la maison, bien sûr...) étant donné que les listes chaînées sont NORMALEMENT (pas toujours, je le reconnais) alloués à l'aide de malloc logique, alors, nous savons que la granularité des allocations est connu. Sur la plupart des systèmes de ce est de 8 octets, ce qui signifie que le bas 3 bits sont toujours des zéros. Considérez - si l'on place la liste liée dans une classe de contrôle de l'accès et de l'utilisation d'un masque de 0x0E par un ou binaire dans la prochaine adresse, alors nous pouvons utiliser la partie inférieure de 3 bits pour stocker une pause de mie Ainsi, nous pouvons écrire une méthode qui vous permettra de stocker notre dernier fil d'ariane - dire 1 ou 2 et de les alterner. Notre méthode qui vérifie une boucle peut ensuite étape à travers chaque nœud (à l'aide de notre méthode suivante) et de vérifier si l'adresse suivante contient le courant du fil d'ariane - si elle ne nous avons une boucle - si ce n'est pas nous masquer la baisse de 3 bits et ajouter actuelle de notre fil d'ariane. Le fil d'ariane algorithme de vérification devrait être mono-thread que vous ne pourriez pas utiliser deux à la fois, mais il permettrait à d'autres threads pour accéder à la liste asynchrone - avec les mises en garde habituelles sur l'ajout/suppression de nœuds. Qu'en pensez-vous? Si d'autres personnes l'impression que c'est une solution valable, je peux écrire des exemples de la classe ... pense Juste que parfois, une nouvelle approche est la bonne et je suis toujours prêt à être dit que j'ai raté de peu le point... Merci à Tous de Marque

Tout d'abord, Créez un Nœud

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

Initialiser le pointeur de tête à l'échelle mondiale

Struct Node* head = NULL;

Insérer des données dans la Liste Liée

void insert(int newdata){

    Node* newNode = new Node();
    newNode->data = newdata;
    newNode->next = head;
    head = newNode;
}

Créer une fonction detectLoop()

void detectLoop(){
    if (head == NULL || head->next == NULL){
        cout<< "\nNo Lopp Found in Linked List";
    }
    else{
        Node* slow = head;
        Node* fast = head->next;
        while((fast && fast->next) && fast != NULL){
            if(fast == slow){
                cout<<"Loop Found";
                break;
            }
            fast = fast->next->next;
            slow = slow->next;
        }
        if(fast->next == NULL){
            cout<<"Not Found";
        }
    }
}

Appel de la fonction main()

int main() 
{ 
    insert(4);
    insert(3);
    insert(2);
    insert(1);

    //Created a Loop for Testing, Comment the next line to check the unloop linkedlist
    head->next->next->next->next = head->next;

    detectLoop();
    //If you uncomment the display function and make a loop in linked list and then run the code you will find infinite loop 
    //display();
}