Finding cycles in a data use case.
There is a task to detect cycles in a data sequence and idea to use Aesop's fable of "The Tortoise and the Hare". As you may remember the hare moves twice as quickly as the tortoise and the distance between them increases by 1 at each step. The idea behind Floyd’s Cycle Detection Algorithm is where there are two pointers - a fast “hare” pointer and a slow “tortoise” pointer.
This approach of 2 pointers is used to find a loop in a linked list. Both pointers will move around the list and if the list is not cyclic, both pointers will never contain the same data. You can test the code below by swithcing/commenting cyclic/looping line.
Floyd’s Cycle Finding Algorithm Python code:
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 # Function to print it the linked LinkedList def printList(self): temp = self.head while(temp): # print temp.data, temp = temp.next def detectLoop(self): slow_p = self.head fast_p = self.head while(slow_p and fast_p and fast_p.next): slow_p = slow_p.next fast_p = fast_p.next.next if slow_p == fast_p: return 1 return 0 # Driver program for testing llist = LinkedList() llist.push(10) llist.push(5) llist.push(15) llist.push(10) llist.push(7) llist.push(5) llist.push(11) llist.push(10) # Create a loop or comment line to eliminate loop - for test llist.head.next.next.next.next = llist.head if(llist.detectLoop()): print ("Loop is found") else: print ("NO Loop is found")
OUT: Loop is found