How to Detect a Cycle in a Linked List Using Floyd’s Tortoise and Hare Algorithm

Floyd’s Tortoise and Hare algorithm detects a cycle in a linked list by moving two pointers at different speeds—one step at a time for the slow pointer and two steps for the fast pointer—returning true if they meet inside a loop or false if the fast pointer reaches the end.

Detecting a cycle in a linked list is a fundamental interview problem solved optimally with constant space using the two-pointer technique known as Floyd’s cycle detection. The kdn251/interviews repository provides battle-tested Java implementations of this algorithm across LeetCode and company-specific modules. This guide walks through the exact implementation found in leetcode/two-pointers/LinkedListCycle.java and explains why this approach guarantees O(n) time complexity with O(1) auxiliary space.

Algorithm Overview

The Tortoise and Hare strategy relies on two pointers traversing the list at different velocities:

• Slow pointer (Tortoise): Advances one node per iteration (slow = slow.next)
• Fast pointer (Hare): Advances two nodes per iteration (fast = fast.next.next)

If the list is acyclic, the fast pointer reaches the end (null) first, terminating the search. If the list contains a cycle, the fast pointer eventually laps the slow pointer from behind, causing them to reference the same node. This meeting point proves the existence of a loop.

Implementation Details

The repository implements this logic in the hasCycle(ListNode head) method. You can find identical implementations across multiple interview preparation tracks, including:

• leetcode/two-pointers/LinkedListCycle.java
• company/microsoft/LinkedListCycle.java
• company/amazon/LinkedListCycle.java
• company/bloomberg/LinkedListCycle.java

The Core Method

According to the source code in leetcode/two-pointers/LinkedListCycle.java, the implementation handles edge cases first, then enters a traversal loop:

public boolean hasCycle(ListNode head) {
    // Edge case: empty list or single node without a next pointer → no cycle
    if (head == null || head.next == null) {
        return false;
    }

    // Initialize pointers
    ListNode slow = head;          // moves 1 step
    ListNode fast = head.next;     // moves 2 steps (starts one step ahead)

    // Traverse until fast reaches the end or meets slow
    while (fast != null && fast.next != null && fast != slow) {
        slow = slow.next;          // one step
        fast = fast.next.next;     // two steps
    }

    // If fast and slow met, a cycle exists
    return fast == slow;
}

Key implementation details:

1. Initialization: The fast pointer starts at head.next rather than head to ensure the while-loop condition fast != slow works correctly from the first iteration.
2. Null checks: The loop condition verifies both fast != null and fast.next != null to prevent NullPointerException when advancing the fast pointer.
3. Termination: The method returns true only when fast == slow, confirming the pointers converged inside a cycle.

Practical Code Examples

Example 1: Handcrafted Cycle Detection

// Build nodes
ListNode a = new ListNode(1);
ListNode b = new ListNode(2);
ListNode c = new ListNode(3);
a.next = b;
b.next = c;
c.next = a;               // creates a cycle (c → a)

// Detect cycle
Solution sol = new Solution();
System.out.println(sol.hasCycle(a)); // prints: true

Example 2: Dynamic List with Injected Cycle

// Assume we have a utility that builds a linked list from an array
int[] values = {4, 5, 6, 7};
ListNode head = ListBuilder.fromArray(values); // no cycle initially

Solution sol = new Solution();
System.out.println(sol.hasCycle(head)); // prints: false

// Introduce a cycle for testing
head.next.next.next.next = head.next; // tail points to second node
System.out.println(sol.hasCycle(head)); // prints: true

Example 3: LeetCode-Style Runner

public class Main {
    public static void main(String[] args) {
        // Example list: 1 → 2 → 3 → 4 → 2 (cycle starts at node with value 2)
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n2; // creates cycle

        Solution solution = new Solution();
        System.out.println(solution.hasCycle(n1)); // true
    }
}

Why This Algorithm Works

In an acyclic list, the fast pointer moves twice as fast toward the null terminator. Since it starts ahead and moves two steps per iteration, it will always reach null before or at the same time the slow pointer reaches the final node.

In a cyclic list, once both pointers enter the loop, the distance between them changes by exactly one node per iteration (the fast pointer gains one node on the slow pointer each step). Because the loop length is finite, the fast pointer will eventually close the gap and occupy the same node as the slow pointer, confirming the cycle. This convergence is mathematically guaranteed regardless of the cycle's length or entry point.

Complexity Analysis

• Time Complexity: O(n) where n is the number of nodes. In the worst case, the algorithm traverses the list once before finding the cycle or reaching the end.
• Space Complexity: O(1) auxiliary space. The solution uses only two pointer variables (slow and fast) regardless of input size, unlike hash-based approaches that require O(n) space to store visited nodes.

Summary

• Floyd’s Tortoise and Hare algorithm uses two pointers moving at 1x and 2x speeds to detect cycles without extra data structures.
• The hasCycle() method in leetcode/two-pointers/LinkedListCycle.java initializes fast at head.next and iterates until pointers meet or fast reaches null.
• This approach guarantees linear time complexity while maintaining constant space overhead, making it optimal for embedded or memory-constrained environments.
• The kdn251/interviews repository duplicates this implementation across company-specific directories (Microsoft, Amazon, Bloomberg), demonstrating its universal applicability in technical interviews.

Frequently Asked Questions

Why does Floyd’s algorithm use two pointers moving at different speeds?

The different speeds ensure that if a cycle exists, the fast pointer will eventually lap the slow pointer from behind. If both pointers moved at the same speed, they would maintain a constant distance inside a cycle and never meet unless they started at the exact same node. The 2:1 speed differential guarantees the distance between them decreases by one node per iteration inside the loop, forcing convergence.

Can I use a HashSet to detect a cycle instead of Floyd’s algorithm?

Yes, but it requires O(n) space complexity. You would traverse the list while storing node references in a HashSet<ListNode>, returning true if set.add(node) returns false (indicating the node was visited before). While simpler to implement, this approach consumes memory proportional to the list length, whereas Floyd’s algorithm detects a cycle in a linked list using only two pointers with O(1) space.

What happens if both pointers start at the head instead of offsetting the fast pointer?

If both slow and fast start at head and you check for equality after moving both pointers, the loop condition must be structured carefully to avoid immediate false positives (they start equal). The implementation in leetcode/two-pointers/LinkedListCycle.java avoids this by initializing fast = head.next, ensuring the first comparison happens after at least one movement. Both initialization patterns work if the loop logic is adjusted accordingly.

How do I find the start of the cycle once detected?

Once the tortoise and hare meet, reset one pointer to the head while keeping the other at the meeting point. Then advance both pointers one step at a time. The node where they meet again is the start of the cycle. This works because the distance from the head to the cycle start equals the distance from the meeting point to the cycle start when measured along the loop.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}