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
slowandfastboth start at the head. Each pass movesslowone node andfasttwo nodes.- In a straight list,
fastreaches the end (None) first, so there is no loop. - In a list with a loop,
fastcan never reach an end. It goes round the loop and gains one node onslowevery pass, so they land on the same node. slow is fastcompares 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:
fastreaches node 5, thenfast.next.nextisNoneand the loop ends. - Watch the arrow from 6 back to 3 appear when
nodes[-1].nextis 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