Fast and Slow Pointers

Linked Lists: lesson 5 of 6

One hop versus two finds the middle in one pass.

Lesson 5 of 6 · 5 min

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)       # 30

Your 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: 30

Mini quiz

1 / 3

Fast and Slow Pointers