Python program to detect cycles in linked list

When any node in the linked list does not point to NULL, it is said that there is a cycle in the linked list. The last node will point to the previous node in the linked list, creating a loop. A circular linked list has no end point.

In the example below, the last node (node ​​5) does not point to NULL. Instead, it points to node 3 and establishes a loop. Therefore, the above linked list is endless.

Algorithm fast and slow to get two pointers

• Both pointers will initially point to the HEAD of the linked list.

• The slow pointer always increases by one, and the fast pointer always increases by two.

• At any time, if the fast pointer and the slow pointer point to the same node, the linked list is said to have a cycle.

Consider the following linked list example where the last node points to the second node -

Example

Both the slow pointer and the fast pointer point to the same node. Therefore, it can be concluded that the given linked list contains a 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()

Output

A cycle was detected in the linked list.

The linked list elements are: 1 2 3 4 

A loop has been detected in the linked list

The above is the detailed content of Python program to detect cycles in linked list. For more information, please follow other related articles on the PHP Chinese website!