Fast and slow pointers means walking a linked list with two references at different speeds, usually one node per step for slow and two for fast. Because the gap between them changes in a predictable way, you can detect a cycle, find the middle, or find the nth node from the end in a single pass with O(1) extra memory. This is also called Floyd’s tortoise and hare algorithm.
All the code below is Python and was run on the sample lists shown. The node class and a small helper to build lists are in the first block.
The setup
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(values, cycle_to=None):
"""Build a list from values; if cycle_to is an index, link the tail back to that node."""
dummy = tail = ListNode()
nodes = []
for v in values:
tail.next = ListNode(v)
tail = tail.next
nodes.append(tail)
if cycle_to is not None:
tail.next = nodes[cycle_to]
return dummy.next
Every problem below uses the same loop shape:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
The condition fast and fast.next is the part people get wrong. You need both checks, in this order, because fast.next.next crashes if fast is None or fast.next is None. The loop ends when fast falls off the end, and at that moment slow is at the halfway point.
1. Detect a cycle
If the list has no cycle, fast reaches None and the loop ends. If there is a cycle, both pointers end up inside it, and fast gains exactly one node on slow every step. A gap that closes by one each step cannot be jumped over, so they must land on the same node.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
print(has_cycle(build([1, 2, 3, 4, 5]))) # False
print(has_cycle(build([1, 2, 3, 4, 5], cycle_to=2))) # True
Compare nodes with is, not == on values: two different nodes can hold the same value. The alternative is a set of visited nodes, which is simpler to write but uses O(n) memory. Fast and slow pointers use O(1).
2. Find where the cycle starts
This is the classic follow-up (“Linked List Cycle II”). Once the pointers meet, reset one of them to the head and move both one step at a time. They meet again at the first node of the cycle.
def cycle_start(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
return None
start = cycle_start(build([1, 2, 3, 4, 5], cycle_to=2))
print(start.val) # 3
print(cycle_start(build([1, 2, 3]))) # None
Why it works: let a be the number of nodes before the cycle, c the cycle length, and k how far into the cycle the meeting point is. When they meet, slow has taken a + k steps and fast has taken twice that. Both are at the same spot, so the extra distance a + k is a whole number of laps: a + k = m·c. Rearranged, a = m·c – k, which says that walking a more steps from the meeting point lands on the cycle start. A pointer from the head also needs a steps to get there, so they arrive together.
3. Find the middle node
When fast has moved to the end, slow has moved half as far.
def middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
print(middle(build([1, 2, 3, 4, 5])).val) # 3
print(middle(build([1, 2, 3, 4, 5, 6])).val) # 4
For an even-length list this returns the second of the two middle nodes. If a problem wants the first one (you need it to split a list in two, for instance), change the loop condition to while fast.next and fast.next.next. Check which one your problem asks for and test with both an odd and an even list.
4. Remove or find the nth node from the end
Here the pointers move at the same speed, but you give fast a head start of n nodes. When fast reaches the last node, slow is just before the node you want. Starting both at a dummy node before the head handles the case where the head itself is removed.
def remove_nth_from_end(head, n):
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
def to_list(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
print(to_list(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2))) # [1, 2, 3, 5]
print(to_list(remove_nth_from_end(build([1, 2, 3, 4, 5]), 5))) # [2, 3, 4, 5]
This code assumes n is between 1 and the list length, as most versions of the problem guarantee. If it might not be, check while advancing fast. You can practice this exact problem in the Remove Nth Node From End Of List lesson.
5. Check for a palindrome
A list cannot be indexed from both ends, so the trick is to find the middle, reverse the second half in place, and compare the halves.
def is_palindrome(head):
if not head:
return True
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# reverse everything after slow
prev, cur = None, slow.next
while cur:
cur.next, prev, cur = prev, cur, cur.next
left, right = head, prev
while right:
if left.val != right.val:
return False
left, right = left.next, right.next
return True
print(is_palindrome(build([1, 2, 3, 2, 1]))) # True
print(is_palindrome(build([1, 2, 2, 1]))) # True
print(is_palindrome(build([1, 2, 3]))) # False
This runs in O(n) time and O(1) space, but it modifies the list. In an interview, say so, and mention that you can reverse the second half again before returning if the caller needs the original list. Reversing a list is its own pattern; see in-place reversal of a linked list or the Reverse Linked List lesson.
It is not only for linked lists
Any sequence that is produced by repeatedly applying a function can have a cycle, and Floyd’s method finds it without storing what it has seen. The standard example is “Happy Number”: repeatedly replace a number with the sum of the squares of its digits; it either reaches 1 or loops forever.
def is_happy(n):
def step(x):
return sum(int(d) ** 2 for d in str(x))
slow, fast = n, step(n)
while fast != 1 and slow != fast:
slow = step(slow)
fast = step(step(fast))
return fast == 1
print(is_happy(19)) # True
print(is_happy(2)) # False
“Find the Duplicate Number” (an array of n+1 values in the range 1 to n, treated as next-pointers) uses the same idea, including the cycle-start step.
Complexity
| Problem | Time | Extra space |
|---|---|---|
| Detect cycle | O(n) | O(1) |
| Find cycle start | O(n) | O(1) |
| Middle node | O(n) | O(1) |
| Nth from end | O(n) | O(1) |
| Palindrome check | O(n) | O(1) |
The cycle case is O(n) because once slow enters the cycle, fast catches it in at most one lap of the cycle.
Common mistakes
- Wrong loop condition.
while fast.next.nextcrashes on empty and one-node lists. Usewhile fast and fast.next. - Comparing values instead of nodes. A list like 1 -> 2 -> 1 has repeated values and no cycle.
- Starting
fastandslowat different nodes and then forgetting that it shifts which middle you get, or breaking the cycle-start proof. If you startfastathead.next, the “reset and walk together” step no longer lands on the cycle start. - Skipping the dummy node when the operation may remove the head.
- Not testing the edge cases: empty list, one node, two nodes, and a cycle that points back to the head.
When to reach for it
Think of fast and slow pointers when a linked list problem asks for something relative to the end or the middle, when you must detect a loop without extra memory, or when a sequence is generated by a function and might repeat. If you can afford O(n) memory, a hash set is often easier to get right, so say that you considered it. For arrays, the related two-pointer and sliding window patterns cover similar ground; our sliding window guide is a good next read, and the Linked Lists lesson covers the basics if the node class above is unfamiliar.
