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.
Python Knowledge Base: Make coding great again.
- Updated:
2024-07-26 by Andrey BRATUS, Senior Data Analyst.
Floyd's Cycle Finding Algorithm Python code:
Floyd's Cycle Finding Algorithm code output:
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.
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