Floyd's Linked List Cycle Finding Algorithm¶
Given a linked list where the starting point of that linked list is denoted by head, and there may or may not be a cycle present. For instance:

Here we need to find out the point C, i.e the starting point of the cycle.
Proposed algorithm¶
The algorithm is called Floyd’s Cycle Algorithm or Tortoise And Hare algorithm. In order to figure out the starting point of the cycle, we need to figure out of the the cycle even exists or not. So, it involved two steps: 1. Figure out the presence of the cycle. 2. Find out the starting point of the cycle.
Step 1: Presence of the cycle¶
- Take two pointers
- Both of them will point to head of the linked list initially.
- Check if at any point they point to the same node before any one(or both) reach null.
- If they point to any same node at any point of their journey, it would indicate that the cycle indeed exists in the linked list.
- If we get null, it would indicate that the linked list has no cycle.

Now, that we have figured out that there is a cycle present in the linked list, for the next step we need to find out the starting point of cycle, i.e., C.
Step 2: Starting point of the cycle¶
- Reset the
- Move both pointers one step at a time.
- The point they will meet at will be the starting point of the cycle.
// Presence of cycle
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow==fast){
return true;
}
}
return false;
}
// Assuming there is a cycle present and slow and fast are point to their meeting point
slow = head;
while(slow!=fast){
slow = slow.next;
fast = fast.next;
}
return slow; // the starting point of the cycle.
Why does it work¶
Step 1: Presence of the cycle¶
Since the pointer
slow: 0 --> 1 --> 2 --> 3 --> 4 (distance covered)
fast: 0 --> 2 --> 4 --> 6 --> 8 (distance covered)
diff: 0 --> 1 --> 2 --> 3 --> 4 (difference between distance covered by both pointers)
Step 2: Starting point of the cycle¶
Lets try to calculate the distance covered by both of the pointers till they point they met within the cycle.

Resolving the formula we get:
where
This basically means that