Using Hash Maps for Cycle Detection (Linked List, Array, Graph)

You know Floyd's cycle detection (tortoise and hare). It's clever, uses O(1) space.

But sometimes hash maps are simpler and more intuitive.

This guide shows you when to use hash maps for cycle detection and when to use Floyd's.

The Hash Map Approach

The pattern

Store visited nodes/states in a set. If you see a node again, there's a cycle.

def hasCycle(head):
    seen = set()
    current = head
    
    while current:
        if current in seen:
            return True  # Cycle detected
        seen.add(current)
        current = current.next
    
    return False  # No cycle

Time: O(n)
Space: O(n)

When to Use Hash Map

Use hash map when:

✅ Space is not critical (O(n) is acceptable)
✅ Simplicity matters (easier to understand)
✅ Need to find cycle start (store indices/nodes)
✅ Complex state (not just linked list)

Example 1: Linked List Cycle

def detectCycle(head):
    """Find where cycle starts."""
    seen = {}
    current = head
    index = 0
    
    while current:
        if current in seen:
            return current  # Cycle starts here
        seen[current] = index
        current = current.next
        index += 1
    
    return None

Why hash map: Easy to track where cycle starts.

Example 2: Happy Number

def isHappy(n):
    """Detect cycle in number transformation."""
    seen = set()
    
    while n != 1:
        if n in seen:
            return False  # Cycle detected
        seen.add(n)
        n = sum(int(d)**2 for d in str(n))
    
    return True

Why hash map: State is a number, not a linked list node.

When to Use Floyd's Algorithm

Use Floyd's when:

✅ Space is critical (need O(1))
✅ Simple linked list (two pointers work)
✅ Don't need cycle details (just yes/no)

Example: Linked List Cycle

def hasCycle(head):
    """Floyd's tortoise and hare."""
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True  # Cycle detected
    
    return False

Time: O(n)
Space: O(1)

Why Floyd's: O(1) space, elegant for linked lists.

Comparison

When Each Is Better

Hash map is better for:

• Happy Number (number transformation)
• Find Duplicate Number (array as graph)
• Complex state spaces
• When you need cycle details

Floyd's is better for:

• Linked List Cycle (O(1) space)
• Simple yes/no detection
• Space-constrained problems
• Classic linked list problems

Summary

Hash map approach:

• Store visited nodes in set
• O(n) space, O(n) time
• Simple and intuitive

When to use:

• Space not critical
• Need cycle details
• Complex state

Floyd's algorithm:

• Two pointers (slow/fast)
• O(1) space, O(n) time
• Clever but tricky

When to use:

• Space critical
• Simple linked list
• Just need yes/no

The rule: Use hash map for simplicity, Floyd's for space optimization.

Next steps:

• Study the complete hash map guide
• Learn hash map vs other structures

Choose the right approach for the problem.