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's a solution so elegant it uses O(1) space instead.

The key insight is that if there's a cycle, two pointers moving at different speeds will eventually meet. It's like two runners on a circular track - the faster one will catch up to the slower one. This mathematical property allows us to detect cycles without storing any visited nodes.

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 track visited nodes, checking if we encounter a node we've seen before.

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
}

This works, but it uses O(n) extra space for the Set. For large lists, this isn't ideal. I wondered if I could do better.

The Fast and Slow Pointers Insight

Then I learned about Floyd's Cycle Detection Algorithm (also called the "tortoise and hare" algorithm). The idea is elegant:

• Use two pointers moving at different speeds
• Slow pointer moves one step at a time
• Fast pointer moves two steps at a time
• If there's a cycle, they'll eventually meet
• If there's no cycle, the fast pointer hits null first

The mathematical intuition: if there's a cycle, the fast pointer will eventually "lap" the slow pointer. The distance between them decreases by 1 each step (fast moves 2, slow moves 1), so they'll meet.

The Solution

function hasCycle(head) {
    if (head === null || head.next === null) {
        return false; // Can't have a cycle with 0 or 1 nodes
    }
    
    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
}

How It Works

Let me trace through an example with a cycle:

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 3→4→3)
• slow === fast → return true!

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

• Initial: slow = 1, fast = 2
• Step 1: slow = 2, fast = 4
• Step 2: slow = 3, fast = null (fast.next is null)
• Exit loop, return false

Why This Works

The algorithm works because of the mathematical property:

• If there's a cycle: The fast pointer will eventually enter the cycle, and since it moves faster, it will catch up to the slow pointer
• If there's no cycle: The fast pointer will reach null first (since it moves faster)
• The distance decreases: Each step, the distance between pointers decreases by 1 (fast moves 2, slow moves 1), guaranteeing they'll meet if there's a cycle

Complexity Analysis

Time Complexity: O(n)

• In the worst case (no cycle), we traverse the list once: O(n)
• If there's a cycle, we'll detect it 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 empty lists and single-node lists (they can't have cycles)
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
}

Key Takeaways

• Fast and slow pointers can detect cycles in O(n) time and O(1) space
• This is much better than storing visited nodes (O(n) space)
• 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 really showed me the power of the fast and slow pointers technique. It's become one of my favorite solutions because of how elegant it is. The fact that we can detect cycles without storing any visited nodes still amazes me. Once you understand the pattern, you'll see it applies to many similar problems.