Skip to content
BytePatterns

Detect a Cycle

Linked Lists: lesson 6 of 6

If the list loops, the fast pointer laps the slow one.

Lesson 6 of 6 · 5 min

Detect a Cycle

Step 1 of 9

Same two pointers as the midpoint trick. On a straight list, watch what happens to fast.

The Idea

Run the same one-hop and two-hop pointers. On a straight list, fast falls off the end. Inside a loop it can never fall off, and since it closes the gap by one node per step, it must eventually land on slow. Meeting means a cycle.

Real-World Example

A misconfigured web redirect does this to your browser. Page A forwards to B, B to C, and C quietly forwards back to B. Nothing errors and nothing loads, so the browser gives up only because it noticed it was going in circles.

The Code

class Node:
    def __init__(self, v): self.value, self.next = v, None

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next          # one step
        fast = fast.next.next     # two steps
        if slow is fast:          # fast lapped slow
            return True
    return False                  # ran off the end: no loop

a = Node(1); b = Node(2); c = Node(3)
a.next = b; b.next = c; c.next = b   # 3 links back to 2
print(has_cycle(a))                  # True

Your turn

Put the steps in the right order.

  1. Return True, because the pointers landed on the same node
  2. Move slow one node and fast two nodes
  3. Start slow and fast on the head node
  4. Return False, because fast ran out of list
  5. Check whether slow and fast are now the same node

Mini quiz

1 / 3

How does the algorithm prove there is no cycle?