Program Python untuk mengesan kitaran dalam senarai terpaut

Apabila mana-mana nod dalam senarai terpaut tidak menghala ke NULL, dikatakan terdapat kitaran dalam senarai terpaut. Nod terakhir akan menunjuk ke nod sebelumnya dalam senarai terpaut, mencipta gelung. Senarai pautan bulat tidak mempunyai titik akhir.

Dalam contoh di bawah, nod terakhir (nod 5) tidak menunjuk kepada NULL. Sebaliknya, ia menunjuk ke nod 3 dan mewujudkan gelung. Oleh itu, senarai pautan di atas tidak berkesudahan.

Algoritma cepat dan lambat untuk mendapatkan dua mata

• Kedua-dua penunjuk pada mulanya akan menghala ke KETUA senarai terpaut.

• Penunjuk perlahan sentiasa meningkat satu, dan penunjuk cepat sentiasa meningkat dua.

• Pada bila-bila masa, jika penunjuk pantas dan penunjuk perlahan menghala ke nod yang sama, senarai terpaut itu dikatakan mempunyai kitaran.

Pertimbangkan contoh senarai terpaut berikut di mana nod terakhir menghala ke nod kedua -

Contoh

Kedua-dua penunjuk perlahan dan penunjuk pantas menghala ke nod yang sama. Oleh itu, boleh disimpulkan bahawa senarai pautan yang diberikan mengandungi kitaran.

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

Output

Satu kitaran telah dikesan dalam senarai terpaut.

The linked list elements are: 1 2 3 4 

A loop has been detected in the linked list

Atas ialah kandungan terperinci Program Python untuk mengesan kitaran dalam senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!