Problem Statement

Given the head of a linked list, return true if the linked list contains a cycle, and false otherwise. A cycle exists if some node in the list can be reached again by continuously following the next pointer.

How the Algorithm Works

💡 One Sentence Rule (Key Insight)

Use two pointers moving at different speeds (slow and fast); if a cycle exists, the fast pointer will eventually catch up to the slow pointer inside the cycle.

Algorithm Overview

The Fast & Slow Pointers (Floyd's Cycle Detection) approach uses two pointers that move at different speeds. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there's a cycle, these pointers will eventually meet inside the cycle, similar to runners on a circular track where the faster runner eventually laps the slower one.

Step-by-Step Process

When traversing the linked list with two pointers:

  1. Initialize both pointers at head ← Start synchronized for relative speed detection
  2. Move slow by 1, fast by 2 steps ← Different speeds enable cycle detection
  3. Check if pointers meet ← Meeting confirms cycle existence
  4. If fast reaches null ← No cycle exists, list terminates

Why It Works: If a cycle exists, the fast pointer enters the cycle first. Once both pointers are in the cycle, the fast pointer closes the gap by one node per iteration (since it moves 2 steps vs slow's 1 step). Eventually, the gap becomes zero and they meet.

Input

head = [3,2,0,-4], pos = 1

Where pos indicates the index of the node where the tail connects back to (creating a cycle at node with value 2).

Output

true

Solution

def has_cycle(head):
    """
    Detect if a linked list contains a cycle using Floyd's algorithm.
    
    Args:
        head: Head node of the linked list
        
    Returns:
        bool: True if cycle exists, False otherwise
    """
    slow, fast = head, head
    
    while fast and fast.next:
        slow = slow.next          # Move slow by 1 step
        fast = fast.next.next     # Move fast by 2 steps
        
        if slow == fast:          # Pointers met - cycle detected!
            return True
    
    return False                  # Fast reached end - no cycle

Complexity Analysis

Time Complexity: O(n)

  • If no cycle: Fast pointer traverses n nodes until reaching null
  • If cycle exists: Once both pointers are in the cycle, they meet within the cycle length iterations
  • Overall: Linear time relative to list length

Space Complexity: O(1)

  • Only two pointer variables used, regardless of input size
  • No additional data structures required
  • Constant auxiliary space

Example walkthrough for [3,2,0,-4] with cycle at position 1:

  1. Initialize: slow = head (3), fast = head (3) → Both start at node 3
  2. Move: slow = 2, fast = 0 → Slow moves 1 step, fast moves 2 steps
  3. Move: slow = 0, fast = 2 → Continue traversal
  4. Move: slow = -4, fast = -4 → Pointers meet! ✓ Cycle detected

Without a cycle (e.g., [1,2,3,4]):

  1. Initialize: slow = 1, fast = 1
  2. Move: slow = 2, fast = 3
  3. Move: slow = 3, fast = null → Fast reached end
  4. Result: No cycle detected

Why the gap closes: Inside a cycle, the fast pointer gains 1 node per iteration on the slow pointer. If the gap is d nodes, it closes to d-1, then d-2, ..., until 0 (meeting).

Core Observations

Why two different speeds?

  • If both moved at the same speed, they'd never meet even with a cycle
  • Moving at different speeds creates relative motion that enables detection

Why check fast and fast.next?

  • Fast moves 2 steps, so we need to ensure fast.next exists
  • If either is null, we've reached the end (no cycle)

Alternative approaches:

  • Hash Set: Store visited nodes, check for duplicates - O(n) space
  • Modify nodes: Mark visited nodes by changing values - destructive
  • Fast & Slow Pointers: O(1) space, non-destructive - optimal

Key Insights

  1. Speed differential is critical: The 2:1 speed ratio ensures detection without missing the cycle
  2. Meeting is inevitable: In a cycle, the faster pointer will always catch the slower one
  3. Null check prevents errors: Always verify fast.next exists before accessing fast.next.next
  4. No extra space needed: Unlike hash set approaches, this uses constant space
  5. Works for any cycle position: Whether the cycle starts at the beginning or end doesn't matter

Common Mistakes

  • ❌ Not checking fast.next before accessing fast.next.next

  • ❌ Starting pointers at different positions

  • ❌ Using equal speeds for both pointers

  • ❌ Forgetting to return true when pointers meet

  • ✅ Check both fast and fast.next in while condition

  • ✅ Initialize both pointers at head

  • ✅ Use 1:2 speed ratio (slow vs fast)

  • ✅ Return true immediately upon meeting

Related Problems