Fast and Slow Pointers
DSA · Linked Lists
Theory
The fast and slow pointer technique (Floyd's tortoise and hare) moves one pointer one step at a time and another two steps at a time. If the list has a cycle, the fast pointer eventually laps the slow one and they meet; if not, the fast pointer reaches the end. When the fast pointer reaches the end of a list without a cycle, the slow pointer is at the middle.
Why we use it
It detects cycles and finds middles in O(n) time with O(1) extra space, without storing visited nodes.
When to use it
Use it for cycle detection, finding the middle node, palindrome linked lists, and finding the start of a cycle.
How it works
- slow = head, fast = head
- fast and fast.next exist? Yes: slow moves 1, fast moves 2. No: No cycle (fast reached the end).
- slow == fast? Yes: Cycle detected. No: Continue moving.
- Done
Syntax
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: cycle found
# no cycle: slow is the middleExample
class Node:
def __init__(self, val):
self.val = val
self.next = None
nodes = [Node(i) for i in range(1, 8)]
for a, b in zip(nodes, nodes[1:]):
a.next = b
slow = fast = nodes[0]
while fast and fast.next:
slow = slow.next
fast = fast.next.next
print("Middle node:", slow.val)
nodes[-1].next = nodes[2] # create a cycle
slow = fast = nodes[0]
has_cycle = False
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
has_cycle = True
break
print("Cycle detected:", has_cycle)Key points
- Slow moves 1 step, fast moves 2
- They meet only if there is a cycle
- Slow ends at the middle when fast ends
- O(1) extra space