Floyd's Cycle Detection Algorithm

Overview

Floyd's Cycle Detection Algorithm, also known as the Tortoise and Hare Algorithm, is used to identify cycles within a data structure such as a linked list. A cycle occurs when a node's next pointer points to a previous node, creating a loop.

The algorithm uses two pointers: a slow pointer and a fast pointer. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle, the fast pointer will eventually catch up to the slow pointer. If the pointers meet, a cycle exists; otherwise, the sequence does not contain a cycle.

General steps of the algorithm:

Initialize two pointers, both starting at the head of the list.
Move the slow pointer one step at a time.
Move the fast pointer two steps at a time.
If there is a cycle, the fast pointer will eventually meet the slow pointer.
If the pointers meet, a cycle exists; otherwise, the sequence does not contain a cycle.

Python Implementation

def check_cycle(head): 
	if not head: 
		return False 
	
	slow = head 
	fast = head 
	
	while fast and fast.next: 
		slow = slow.next 
		fast = fast.next.next 
	
	if slow == fast: 
		return True 
	return False

Complexity Analysis

Time Complexity

Worst Case: O(n). In the worst case, consider a list that forms a perfect loop. In such a scenario, the fast pointer will have to travel through the entire list to reach the slow pointer, which will take O(n) time.
Best Case: O(1). In the best case, consider a single node which points to itself. In such a scenario, the algorithm will terminate in O(1) time.

Space Complexity

The algorithm uses O(1) space since it only requires two pointers.

Finding the Start of the Cycle

Floyd's Cycle Detection Algorithm can be modified to find the node where the cycle begins. This is achieved by determining the first intersection point of the slow and fast pointers within the cycle. The key idea behind this is that distance from the starting point of the list to the start of the cycle is equal to the distance from the intersection point to the start of the cycle. Here is an explanation of why this is true.

Consider a linked list with a cycle. Let:

A be the start of the list.
C be the start of the cycle.
B be the first intersection point of the slow and fast pointers.
x be the length of the cycle.

Thus, $A C$ represents the distance from the start of the list to the start of the cycle, and $B C$ represents the distance from the first intersection point to the start of the cycle.

The slow pointer travels a distance of $A C + C B$ , while the fast pointer travels a distance of $A C + x + C B$ . We also know that the fast pointer travels twice as fast as the slow pointer, so the fast pointer also travels a distance of $2 (A C + C B)$ . We can then set up the equation:

\begin{aligned} 2 (A C + C B) & = A C + x + C B \\ 2 A C + 2 C B & = A C + B C + C B + C B \\ 2 A C & = A C + B C \\ A C & = B C \end{aligned}

Thus, we see that the distance from the start of the list to the start of the cycle and the distance from the first intersection point to the start of the cycle are equal.

To find the start of the cycle, we just need to create 2 slow pointers: one at the start of the list and one at the intersection point. Then, we simply need to move each pointer until they intersection, which will be the start of the cycle in the linked list.

Python Implementation

def determine_cycle_start(head): 
	if not head: 
		return None 
	
	slow = head 
	fast = head 

	# Determine if a cycle exists. If a cycle exists, get the first intersection point of the two pointers
	while fast and fast.next: 
		slow = slow.next 
		fast = fast.next.next 
	
		if slow == fast: break 

	# If no cycle exists
	if not fast or not fast.next: 
		return None 
		
	# Find the start of the cycle 
	slow2 = head 
	while slow != slow2: 
		slow = slow.next 
		slow2 = slow2.next 
	return slow