Fast and Slow Pointers
Linked Lists: lesson 5 of 10
One hop versus two finds the middle in one pass.
Lesson 5 of 10 · 5 min
Fast and Slow Pointers
Step 1 of 7
slow hops0fast hops0
slow
fast
·
10•
·
20•
·
30•
·
40•
·
50•
∅
Both pointers start on the head. slow takes one hop per turn, fast takes two.
The Idea
Send two pointers from the head, one moving a node at a time and the other two. The fast pointer runs out of list after n/2 steps of the slow one, so wherever slow stands is the middle. One pass, O(1) space, no length counter.
Real-World Example
A proofreader and a skimmer open the same manuscript on page one. The skimmer flips two sheets for every one the proofreader turns. The moment the skimmer runs out of pages, the proofreader is standing exactly halfway through.
The Code
class Node:
def __init__(self, v): self.value, self.next = v, None
def middle(head):
slow = fast = head
while fast and fast.next: # need two nodes left to jump
slow = slow.next # one hop
fast = fast.next.next # two hops
return slow # fast hit the end, slow is halfway
head = Node(10)
head.next = Node(20); head.next.next = Node(30)
head.next.next.next = Node(40); head.next.next.next.next = Node(50)
print(middle(head).value) # 30Your turn
Fill in the blank.
class Node:
def __init__(self, v): self.value, self.next = v, None
head = Node(10); head.next = Node(20); head.next.next = Node(30)
head.next.next.next = Node(40); head.next.next.next.next = Node(50)
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = ___
print(slow.value) # should print the middle: 30Mini quiz
1 / 3