Linked List Cycle

Linked List Cycle asks a simple yes/no question — but the elegant answer, Floyd's tortoise and hare, is a classic interview favorite. It detects a loop using two pointers and zero extra memory.

The slow way first

The obvious idea: walk the list and remember every node you have visited in a hash set. The moment you reach a node already in the set, you have found a cycle. That works and is O(n) time — but it costs O(n) extra space for the set.

The question to ask: can I detect the loop without storing every node? Yes — by racing two pointers at different speeds.

The idea: two pointers, two speeds

Send two pointers down the list from the head. slow advances one node per step; fast advances two. Think of two runners on a track:

• If the list ends (no cycle), the fast runner reaches the finish line (None) and we return False.
• If the list loops, neither runner can escape. The fast runner gains exactly one node on the slow runner every step, so it is guaranteed to lap it — and they land on the same node.

The key insight: meeting can only happen inside a cycle. A meeting is a proof of a loop.

Walk through it

Step through the animation. Both pointers start on node 1. Each step, slow (blue) takes one hop and fast (red) takes two. They pull apart — until fast wraps around the back edge 5 → 3. On the next jump fast lands on node 4, exactly where slow is. slow == fast, so we return True.

Pseudocode

slow = head
fast = head
while fast is not None and fast.next is not None:
    slow = slow.next            # one hop
    fast = fast.next.next       # two hops
    if slow == fast:            # same node?
        return True             # they met -> cycle
return False                    # fast ran off the end -> no cycle

The Python solution

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

• slow = fast = head starts both pointers at the same place.
• The loop guard while fast and fast.next is what catches a non-cyclic list: if fast (or the node after it) is None, the list ended and we fall through to return False.
• slow = slow.next moves one node; fast = fast.next.next moves two.
• Line 6 compares the two nodes (identity), not their values. Equal nodes mean the pointers collided inside a loop.
• No set, no recursion — just two pointers, so the extra space is O(1).

Complexity

Both approaches are O(n) time, but Floyd's needs only two pointers — constant extra space. The fast pointer travels at most about twice around the loop before meeting the slow one, so the running time stays linear.

When this pattern shows up

Practice