Floyd’s Cycle Finding Algorithm.

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.

Floyd’s Cycle Finding Algorithm.



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





See also related topics: