Pattern 3 of 27
Fast and Slow Pointers
Move two pointers through a linked list at different speeds to find cycles, midpoints and offsets in one pass with no extra memory.
- Cost
- O(n) time, O(1) space
- Problems
- 6
When to reach for it
- The input is a linked list, so you cannot jump to an index.
- The question mentions a cycle, the middle node, or the nth node from the end.
- O(1) extra space is required, which rules out a visited set.
How it works
If one pointer moves one node at a time and the other moves two, the fast one reaches the end exactly when the slow one is halfway, which gives the middle. If the list loops, the fast pointer never reaches an end and has to land on the slow one somewhere inside the loop, which proves the cycle. A close relative keeps two pointers a fixed gap apart instead of at different speeds, which turns "nth node from the end" into a single pass.
The template
Written for Middle of the Linked List (write-up)
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # one step
fast = fast.next.next # two steps
return slowSix problems, in learning order
- 1.Linked List CycleLeetCode 141The two pointers meeting at all proves a cycle exists.Easy
- 2.Linked List Cycle IILeetCode 142After they meet, restart one pointer at the head; stepping both by one meets at the cycle start.Not in the curated 370 yet.Medium
- 3.Remove Nth Node From End of ListLeetCode 19A fixed gap of n nodes instead of different speeds.Medium
- 4.Middle of the Linked ListLeetCode 876Slow lands on the middle when fast runs out of list.Easy
- 5.Intersection of Two Linked ListsLeetCode 160Each pointer jumps to the other list's head at its end, so both travel the same total distance.Easy
- 6.Palindrome Linked ListLeetCode 234Find the middle, reverse the second half, compare, then restore it.Easy
What usually goes wrong
- Reading fast.next.next without first checking that fast and fast.next exist.
- On even-length lists, not deciding which of the two middle nodes the question wants.
- Skipping the dummy head in Remove Nth From End and failing when the head itself is removed.
Fast and Slow Pointers, answered
When should I use the fast and slow pointers pattern?
The input is a linked list, so you cannot jump to an index. The question mentions a cycle, the middle node, or the nth node from the end. O(1) extra space is required, which rules out a visited set.
What is the time complexity of fast and slow pointers?
O(n) time, O(1) space. A close relative keeps two pointers a fixed gap apart instead of at different speeds, which turns "nth node from the end" into a single pass.
Which problem should I start with for fast and slow pointers?
Start with Linked List Cycle (LeetCode 141, Easy). The two pointers meeting at all proves a cycle exists. The six problems on this page are in learning order.