Floyd’s Cycle-Finding Algorithm

Basic Algo

Floyd Cycle Algorithm states that:

• Traverse linked list using two pointers.
• Move one pointer(slow_p or tortoise or walker) by one and another pointer(fast_p or hare or runner) by two.
• If these pointers meet at the same node then there is a loop. If pointers do not meet then linked list doesn’t have a loop.

This is also called tortoise and hare approach.

How This Works?

To Check if Cycle Exists

First take one example : head = [3,2,0,-4], pos = 1 and look at this visually,

We will use two pointers fast & slow. The fast one move at the speed of 2X & the slow one move at the speed of 1X intially.

So, we will start traversing both the pointers one by one, hence there is a cycle so fast & slow pointer will gauranteed meet at a point.

As we see in the diagram they have meet at -4 node. Which shows that there is a cycle. But, if there is no loop then, fast will move to null OR fast.next will move to null early before slow on the middle node.

To Find Start Node of Cycle

But our focus is on where the cycle has started. So, for that once they meet [slow == fast] then, we will reset the slow back to head & start moving slow with 1X speed and fast will carry on from where it was previously but with 1X speed

Once slow & fast collab we will return either slow OR fast is same thing. As, they will return tail connects to node index 1

Intuition Behind Starting Point

Now lets look at why the above algorithm works. Lets assume following:

Distance traveled by fast pointer = 2 x Distance Traveled by slow pointer
​
Thus,
(m + n*x + k) = 2 x (m + n*y +k)
​
x -->  Number of complete cyclic rounds made by 
       fast pointer before they meet first time
​
y -->  Number of complete cyclic rounds made by 
       slow pointer before they meet first time
       
 From above, we can conclude,
    m + k = (x-2y)*n
​
Which means m+k is a multiple of n.

	m + k = A * n where A is an integer

So, when the SP and FP meet, that establishes the fact that there is a cycle. This also tells us m+k is multiple of n.

Now if we start moving both pointers again at the same speed such that one pointer (say SP) begins from the head node of the linked list and other pointers (say FP) begins from the meeting point.

When the SP reaches the beginning of the loop (has made m steps), the FP would have made also moved m steps as they are now moving the same pace. Since m+k is a multiple of n and fast starts from k, they would meet at the beginning.

Can they meet before also? No, because the SP enters the cycle first time after m steps.

Source Code

Detecting Cycle

public static boolean hasLoop(ListNode head) {
	ListNode slow = head;
	ListNode fast = head.next;

	while (slow != null && fast != null && slow != fast) {
		if (fast.next == null) {
			break;
		}
		slow = slow.next;
		fast = fast.next.next;
	}

	if (slow != null && fast != null && slow == fast) {
		return true;
	}

	return false;
}

Get the Start Node

public ListNode detectCycle(ListNode head) {
	ListNode slow = head;
	ListNode fast = head;
	
	while(fast != null && fast.next != null){
		slow = slow.next;
		fast = fast.next.next;
		if(slow == fast){
			slow = head;
			while(slow != fast){
				slow = slow.next;
				fast = fast.next;
			}
			return slow;
		}
	}
	return null;
}

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1)