Leetcode - Linked List Cycle Solution

Detecting cycles in linked lists is a classic interview problem. My first solution used a Set to track visited nodes, which worked but used O(n) space. Then I learned about fast and slow pointers (Floyd's Cycle Detection Algorithm). It uses O(1) space instead.

Inside a cycle, the fast pointer advances two nodes per iteration and the slow pointer advances one. Their relative positions repeat modulo the cycle length, so the pointers must meet. No record of visited nodes is necessary.

Understanding the Problem

Given a linked list, determine if it contains a cycle. A cycle means some node points back to a previous node, creating a loop. The challenge is detecting this efficiently, ideally without using extra space proportional to the list size.

My First Approach

I used a Set to record visited nodes. A repeated node indicates a cycle.

function hasCycleNaive(head) {
    let seen = new Set();
    
    while (head !== null) {
        if (seen.has(head)) {
            return true; // Found a cycle!
        }
        seen.add(head);
        head = head.next;
    }
    
    return false; // No cycle
}

The Set records each visited node and needs O(n) extra space. Two pointers can detect a cycle without that collection.

The Fast and Slow Pointers Insight

I then learned about Floyd's Cycle Detection Algorithm (also called the "tortoise and hare" algorithm). It uses these rules:

• Use two pointers moving at different speeds
• Slow pointer moves one step at a time
• Fast pointer moves two steps at a time
• In a cycle, the pointers eventually meet
• Without a cycle, the fast pointer or its next link reaches null

Once both pointers enter the cycle, their relative distance changes by 1 per iteration (fast moves 2, slow moves 1). Within one cycle length, their positions match.

Fast and slow pointer implementation

function hasCycle(head) {
    if (head === null || head.next === null) {
        return false; // An empty list or a null next link cannot form a cycle
    }
    
    let slow = head;        // Moves 1 step at a time
    let fast = head.next;   // Moves 2 steps at a time
    
    while (fast !== null && fast.next !== null) {
        if (slow === fast) {
            return true; // They met! There's a cycle
        }
        slow = slow.next;      // Move slow 1 step
        fast = fast.next.next; // Move fast 2 steps
    }
    
    return false; // Fast hit null, no cycle
}

Pointer trace

For a list with a cycle, the pointers move as follows:

List with cycle: 1 → 2 → 3 → 4 → 5 → 3 (points back to 3)

• Initial: slow = 1, fast = 2
• Step 1: slow = 2, fast = 4 (fast moved 2 steps)
• Step 2: slow = 3, fast = 3 (fast moved from 4→5→3, slow moved 2→3)
• slow === fast → return true!

List without cycle: 1 → 2 → 3 → 4 → null

• Initial: slow = 1, fast = 2
• Step 1: slow = 2, fast = 4
• The loop stops at slow = 2, fast = 4 because fast.next is null
• Return false

Why This Works

The algorithm works because of the mathematical property:

• Cycle present: Both pointers enter the cycle. Their positions must then match within one cycle length.
• Without a cycle: The loop stops when the fast pointer or its next link is null
• Relative distance: Each iteration changes the relative distance by 1 modulo the cycle length (fast moves 2, slow moves 1).

Complexity Analysis

Time Complexity: O(n)

• In the worst case (no cycle), we traverse the list once: O(n)
• After both pointers enter a cycle, they meet within one cycle length: still O(n)
• Each step is O(1), so overall O(n)

Space Complexity: O(1)

• Only using two pointer variables
• No additional data structures
• Constant space regardless of list size

Common Pitfalls

When implementing this, watch out for:

1. Null pointer errors: Always check fast !== null && fast.next !== null before accessing fast.next.next
2. Edge cases: Handle an empty list and a list with one node. A node can form a cycle if it points to itself.
3. Starting positions: Some implementations start both pointers at head, but starting fast at head.next avoids the initial equality check
4. Infinite loops: Make sure your loop condition properly handles the null case

Finding the Cycle Start (Bonus)

If you need to find where the cycle starts, you can extend this algorithm:

function detectCycleStart(head) {
    // First, detect if there's a cycle
    let slow = head;
    let fast = head;
    
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) break; // Found meeting point
    }
    
    if (fast === null || fast.next === null) return null; // No cycle
    
    // Move one pointer to head, keep other at meeting point
    // Move both one step at a time - they'll meet at cycle start
    slow = head;
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow; // This is the cycle start
}

Cycle detection summary

• Fast and slow pointers detect cycles in O(n) time and O(1) space without visited nodes
• The technique works because cycles create a "catch-up" scenario
• This pattern appears in other cycle detection problems (like Happy Number)
• Floyd's algorithm is a classic example of using mathematical properties to optimize algorithms

This problem showed me how the fast and slow pointers technique uses the list's structure instead of extra storage. The same pattern applies to other cycle detection problems.