loopdetection.py

# Python3 program to detect loop
# in the linked list
 
# Node class
class Node:
 
    # Constructor to initialize
    # the node object
    def _init_(self, data):
        self.data = data
        self.next = None
 
 
class LinkedList:
 
    # Function to initialize head
    def _init_(self):
        self.head = None
 
    # Function to insert a new
    # node at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
 
    # Utility function to print it
    # the linked LinkedList
    def printList(self):
        temp = self.head
        while(temp):
            print(temp.data, end=" ")
            temp = temp.next
 
    def detectLoop(self):
        s = set()
        temp = self.head
        while (temp):
 
            # If we already have
            # this node in hashmap it
            # means there is a cycle
            # (Because we are encountering
            # the node second time).
            if (temp in s):
                return True
 
            # If we are seeing the node for
            # the first time, insert it in hash
            s.add(temp)
 
            temp = temp.next
 
        return False
 
 
# Driver program for testing
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(10)
 
# Create a loop for testing
llist.head.next.next.next.next = llist.head
 
if(llist.detectLoop()):
    print("Loop Found")
else:
    print("No Loop ")