pattern heroPT–23LeetCode Extension

Fast and slow pointers

Send two pointers along the list at different speeds. If the list loops, the fast one catches up with the slow one; if not, it reaches the end. Nothing has to be remembered: two pointers are enough.

Variant
P13 Fast and slow pointersCycle · 1×

Example problem: check whether a linked list has a cycle.

head12345678slow
slowfastwhere they meet

Slow starts at the head: 1

slow = 1fast = –cycle = –
01/30
restart · back · play · step
Speed
1function hasCycle(head):
2 slow = head
3 fast = head
4 cycle = false
5 while fast and fast.next are not none:
6 slow = slow.next
7 fast = fast.next.next
8 if slow is fast:
9 cycle = true
10 break
11 return cycle

← → step · space play/pause

How to recognise

a linked list, or any "go to the next" rule, and a question about a cycle, where it starts, or the middle, often with O(1) extra memory.

How to solve problems like this

  1. Start both pointers at the head.
  2. Each step, move slow by one and fast by two. Check first that fast and fast.next exist.
  3. If fast reaches the end, there is no cycle. At that moment slow is at the middle.
  4. If they meet, there is a cycle. To find where it starts, move one pointer back to the head and step both by one until they meet again.

Variant: Middle

The same, but to find the middle: the fast pointer moves twice as fast, so when it reaches the end, the slow one is exactly halfway. The length need not be known.

  1. Start both pointers at the head.
  2. Loop while fast and fast.next both exist: move slow by one and fast by two.
  3. When the loop stops, slow is the middle. With an odd length fast stops on the last node; with an even length it steps off to none, and slow is on the second of the two middle nodes.
  4. The same trick splits a list in half: to check a palindrome list, reverse the half after the middle and compare; to sort a list, sort both halves and merge them.

Variant: n apart

The same, but both pointers move at one speed and the fast one starts n nodes ahead. When it reaches the end, the other is n nodes from the end, without counting the length.

  1. Spot it: a position counted from the end of a linked list, in one pass or without knowing the length.
  2. Put a dummy node in front of the head and start both pointers on it.
  3. Move fast n steps alone. Then move both by one until fast.next is none.
  4. slow is now right before the n-th node from the end: set slow.next = slow.next.next and return dummy.next.
  5. Rotate a list by k the same way: find the k-th node from the end, cut the list before it, and attach the old tail to the old head. Take k modulo the length first.

Where it's used

  • Factoring numbers. Pollard's rho method builds a sequence of numbers that sooner or later loops, and finds the loop with a slow and a fast pointer, without storing the numbers. SymPy has it, for example.
  • Cryptography. Pollard also adapted the rho method to discrete logarithms, and it is the best known general attack on elliptic-curve cryptography. 256-bit keys are chosen so that this attack runs out of time.