Detect Cycle in a Linked List: Tortoise and Hare Guide

The Core Problem

A cycle or loop occurs in a singly linked list when some node's next pointer points back to a previous node in the list. This creates an infinite pathway. If we try to traverse such a list naively, our code will get stuck in an infinite loop.

Our goal is to write an algorithm that returns true if a cycle exists in the linked list, and false if it does not.

Interactive Visualization

Test the algorithm in action using our interactive tool. Use the Next and Prev buttons to watch how the Tortoise (slow pointer) and the Hare (fast pointer) move through the nodes and meet inside the cycle loop.

Floyd's Cycle Finding Algorithm (Tortoise & Hare)

The most optimal way to solve this problem is Floyd's Cycle Finding Algorithm. It uses two pointers moving at different speeds:

• Slow Pointer (Tortoise): Moves forward by one node at a time.
• Fast Pointer (Hare): Moves forward by two nodes at a time.

Why does it work?

If there is no cycle, the fast pointer will eventually reach the end of the linked list (null), and we can conclude that there is no loop.

However, if a cycle exists, the fast pointer will enter the cycle first. Since it moves faster than the slow pointer, it will eventually "catch up" to the slow pointer from behind and meet on the same node.

Imagine two runners on a circular race track. If one runs twice as fast as the other, the faster runner will eventually lap the slower runner.

Code Implementations

Here is the clean implementation of Floyd's Cycle Finding Algorithm in multiple programming languages:

JavaScript / TypeScript

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val: number) {
        this.val = val;
        this.next = null;
    }
}
 
function hasCycle(head: ListNode | null): boolean {
    if (head === null || head.next === null) {
        return false;
    }
 
    let slow: ListNode | null = head;
    let fast: ListNode | null = head;
 
    while (fast !== null && fast.next !== null) {
        slow = slow!.next;           // Tortoise moves 1 step
        fast = fast.next.next;        // Hare moves 2 steps
 
        if (slow === fast) {
            return true;              // Cycle detected!
        }
    }
 
    return false;                     // Reached end, no cycle exists
}

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
def hasCycle(head: ListNode) -> bool:
    if not head or not head.next:
        return False
        
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next          # 1 step
        fast = fast.next.next     # 2 steps
        
        if slow == fast:
            return True           # Cycle detected!
            
    return False                  # No cycle

Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
 
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;         // 1 step
            fast = fast.next.next;    // 2 steps
            
            if (slow == fast) {
                return true;          // Cycle detected!
            }
        }
        
        return false;
    }
}

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the list.
  • If there is no cycle, the fast pointer traverses the list linearly in O(N) steps.
  • If a cycle exists, the pointers will meet within the first full loop traversal of the cycle.
• Space Complexity: O(1) (Constant Space).
  • We only allocate two pointers (slow and fast), regardless of the size of the list. This is much better than the hash-table lookup approach which requires O(N) extra space.

Summary & Key Takeaways

1. Floyd's Algorithm is the optimal way to find cycles in linear data structures without allocating extra memory.
2. If pointers meet, a cycle exists. If the fast pointer reaches null, no cycle exists.
3. Be sure to check boundary conditions: check if head or head.next is initially null to avoid runtime exceptions.

If you are currently studying computer science or prepping for technical assessments, remember that accurate planning is key. Use our free AnaCGPA tools to calculate your cumulative performance statistics and grades!