Python-Programm zum Erkennen von Zyklen in verknüpften Listen

Wenn ein Knoten in der verknüpften Liste nicht auf NULL zeigt, spricht man von einem Zyklus in der verknüpften Liste. Der letzte Knoten zeigt auf den vorherigen Knoten in der verknüpften Liste, wodurch eine Schleife entsteht. Eine zirkulär verknüpfte Liste hat keinen Endpunkt.

Im folgenden Beispiel zeigt der letzte Knoten (Knoten 5) nicht auf NULL. Stattdessen zeigt es auf Knoten 3 und richtet eine Schleife ein. Daher ist die oben verlinkte Liste endlos.

Algorithmus schnell und langsam, um zwei Zeiger zu erhalten

• Beide Zeiger zeigen zunächst auf den HEAD der verknüpften Liste.

• Der langsame Zeiger erhöht sich immer um eins und der schnelle Zeiger erhöht sich immer um zwei.

• Wenn der schnelle Zeiger und der langsame Zeiger jederzeit auf denselben Knoten zeigen, spricht man von einer Schleife der verknüpften Liste.

Betrachten Sie das folgende Beispiel einer verknüpften Liste, bei der der letzte Knoten auf den zweiten Knoten zeigt -

Beispiel

Sowohl der langsame Zeiger als auch der schnelle Zeiger zeigen auf denselben Knoten. Daher kann der Schluss gezogen werden, dass die angegebene verknüpfte Liste einen Zyklus enthält.

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()

Ausgabe

In der verknüpften Liste wurde ein Zyklus erkannt.

The linked list elements are: 1 2 3 4 

A loop has been detected in the linked list

Das obige ist der detaillierte Inhalt vonPython-Programm zum Erkennen von Zyklen in verknüpften Listen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!