Python-Powered Cycling: Discover Floyd's 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.

Python Knowledge Base: Make coding great again.
- Updated: 2024-09-12 by Andrey BRATUS, Senior Data Analyst.

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.

1. Floyd's Cycle Finding Algorithm Python code:

2. ``````
class Node:

# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)

def printList(self):
while(temp):
#             print temp.data,
temp = temp.next

def detectLoop(self):
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.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
if(llist.detectLoop()):
print ("Loop is found")
else:
print ("NO Loop is found")
``````
3. Floyd's Cycle Finding Algorithm code output:

4. OUT: Loop is found