Editor

Detect a cycle in a linked list in Python

Floyd's tortoise and hare finds a loop in a linked list with two pointers: one moves a node at a time, the other two at a time. If the list loops, the fast one laps the slow one and they meet.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. slow and fast both start at the head. Each pass moves slow one node and fast two nodes.
  2. In a straight list, fast reaches the end (None) first, so there is no loop.
  3. In a list with a loop, fast can never reach an end. It goes round the loop and gains one node on slow every pass, so they land on the same node.
  4. slow is fast compares the nodes themselves, not their values, so two different nodes holding the same value never count as a meeting.

What to watch

  • Watch the first run: fast reaches node 5, then fast.next.next is None and the loop ends.
  • Watch the arrow from 6 back to 3 appear when nodes[-1].next is set.
  • Watch the second run: once both are inside the loop, the gap between them shrinks by one node a pass until they meet.

The code

class Node:
    def __init__(self, value):
        self.value = value
        self.next = 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:
            return True              # the hare caught the tortoise
    return False                     # the hare reached the end

nodes = [Node(v) for v in range(1, 7)]
for a, b in zip(nodes, nodes[1:]):
    a.next = b
print("Straight list:", has_cycle(nodes[0]))
nodes[-1].next = nodes[2]            # 6 points back to 3
print("With a loop:", has_cycle(nodes[0]))
Output
Straight list: False
With a loop: True

Open it in the editor · Python Program to Implement a Linked List, explained