Fast and Slow Pointers
The tortoise and the hare.
Send two pointers along a linked list. The slow one moves one step at a time, and the fast one moves two. That simple idea finds the middle of a list, and detects loops, without any extra memory.

- Slow moves one step
- Fast moves two
- Middles and loops
Finding the middle
When the fast pointer reaches the end, the slow pointer has gone exactly half as far. So it's standing on the middle node. Run it. The middle of one to five is three. For one to six, it's four, the second of the two middle nodes.
from node import build
def middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow.value
print(middle(build([1, 2, 3, 4, 5])))
print(middle(build([1, 2, 3, 4, 5, 6])))3 4
Also uses node.py
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def show(head):
vals = []
while head:
vals.append(str(head.value))
head = head.next
print(" -> ".join(vals) + " -> None")Detecting a loop
A broken list might loop back on itself, so walking it would never end. With a loop, the fast pointer eventually laps the slow one, like a faster runner on a track. If they ever meet, there's a loop. If fast reaches the end, there isn't. Run it.
from node import build
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
return True
return False
head = build([1, 2, 3, 4])
print(has_cycle(head))
head.next.next.next.next = head.next
print(has_cycle(head))False True
Also uses node.py
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def show(head):
vals = []
while head:
vals.append(str(head.value))
head = head.next
print(" -> ".join(vals) + " -> None")Summary
Slow and fast pointers find the middle, and detect loops, in O of N time with O of one memory. Next, linked lists with arrows in both directions.
Key takeaways- slow: 1 step, fast: 2
- Middle: where slow stops
- They meet: a loop