Programme Python pour détecter les cycles dans la liste chaînée

Lorsqu'un nœud de la liste chaînée ne pointe pas vers NULL, on dit qu'il y a un cycle dans la liste chaînée. Le dernier nœud pointera vers le nœud précédent dans la liste chaînée, créant une boucle. Une liste chaînée circulaire n’a pas de point final.

Dans l'exemple ci-dessous, le dernier nœud (nœud 5) ne pointe pas vers NULL. Au lieu de cela, il pointe vers le nœud 3 et établit une boucle. Par conséquent, la liste ci-dessus est infinie.

Algorithme rapide et lent pour obtenir deux pointeurs

• Les deux pointeurs pointeront initialement vers le HEAD de la liste chaînée.

• Le pointeur lent augmente toujours de un et le pointeur rapide augmente toujours de deux.

• A tout moment, si le pointeur rapide et le pointeur lent pointent vers le même nœud, la liste chaînée est dite avoir un cycle.

Considérez l'exemple de liste chaînée suivant où le dernier nœud pointe vers le deuxième nœud -

Exemple

Le pointeur lent et le pointeur rapide pointent tous deux vers le même nœud. Par conséquent, on peut conclure que la liste chaînée donnée contient un cycle.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None


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

    def insert_at_the_end(self,newVal):
        newNode=Node(newVal)
        if self.head==None:
            self.head=newNode
            return
        temp=self.head
        while(temp.next):
            temp=temp.next
        temp.next=newNode


    def Print_the_LL(self):
        temp = self.head
        if(temp != None):
          print("\nThe linked list elements are:", end=" ")
          while (temp != None):
            print(temp.val, end=" ")
            temp = temp.next
        else:
          print("The list is empty.")
    def detect_loop(self):
        slow=self.head
        fast=self.head
        while(fast):
            if slow==fast:
                print("\nA loop has been detected in the linked list ")
                return
            slow=slow.next
            fast=fast.next


newList = LinkedList()
newList.insert_at_the_end(1)
newList.insert_at_the_end(2)
newList.insert_at_the_end(3)
newList.insert_at_the_end(4)
newList.Print_the_LL()
print("\n")
newList.head.next.next.next.next=newList.head.next
newList.detect_loop()

Sortie

Un cycle a été détecté dans la liste chaînée.

The linked list elements are: 1 2 3 4 

A loop has been detected in the linked list

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!