Fast and slow pointers

When to use it

Use it when the question is about a place in a chain of unknown length: its middle, a spot counted from the end, or whether it loops.

It belongs to the foundations group: Remember what you have seen, in a shape that makes the next question take one step.

Watch it work

A bus line is stored as a linked list of its stops, and you do not know how many there are. Return the name of the middle stop after one walk along the line. For an even number of stops, return the second of the two middle ones.

Input
head = ["Ash", "Bay", "Elm", "Fir", "Oak", "Pine", "Yew"]

Output
"Fir"

head reaches the code as a linked list: each node has a value, val, and a link to the node after it, next.

The method

1. Start a slow pointer and a fast pointer on the first node
2. Continue while the fast pointer can still take two steps
3. Move the slow pointer one node and the fast pointer two
4. The fast pointer is at the end: the slow one is in the middle

The run, one moment at a time

1. Step 1. Both pointers start on Ash, the first stop. Fast will run ahead to find the end. Slow keeps the middle of the part that fast has covered.

   slow: Ash
   fast: Ash
   

2. Step 2. The fast pointer is on Ash, and Bay comes after it. It can take two steps, so the loop continues.

   slow: Ash
   fast: Ash
   

3. Step 3. Slow moves one stop, to Bay. Fast moves two stops, to Elm. Fast is now 1 stop ahead.

   slow: Bay
   fast: Elm
   

4. Step 2. The fast pointer is on Elm, and Fir comes after it. It can take two steps, so the loop continues.

   slow: Bay
   fast: Elm
   

5. Step 3. Slow moves one stop, to Elm. Fast moves two stops, to Oak. Fast is now 2 stops ahead.

   slow: Elm
   fast: Oak
   

6. Step 2. The fast pointer is on Oak, and Pine comes after it. It can take two steps, so the loop continues.

   slow: Elm
   fast: Oak
   

7. Step 3. Slow moves one stop, to Fir. Fast moves two stops, to Yew. Fast is now 3 stops ahead.

   slow: Fir
   fast: Yew
   

8. Step 2. The fast pointer is on Yew, the last stop. No stop comes after it, so it cannot take two steps. The loop ends.

   slow: Fir
   fast: Yew
   

9. Step 4. Fast walked 6 links while slow walked 3, half as many. So slow is on Fir, the middle stop, with 3 stops before it and 3 after it.

   slow: Fir
   fast: Yew
   

The code

The numbered comments are the steps of the method.

function solve(head) {
  // 1. Start a slow pointer and a fast pointer on the first node
  let slow = head;
  let fast = head;
  // 2. Continue while the fast pointer can still take two steps
  while (fast && fast.next) {
    // 3. Move the slow pointer one node and the fast pointer two
    slow = slow.next;
    fast = fast.next.next;
  }
  // 4. The fast pointer is at the end: the slow one is in the middle
  return slow.val;
}

def solve(head):
    # 1. Start a slow pointer and a fast pointer on the first node
    slow = head
    fast = head
    # 2. Continue while the fast pointer can still take two steps
    while fast and fast.next:
        # 3. Move the slow pointer one node and the fast pointer two
        slow = slow.next
        fast = fast.next.next
    # 4. The fast pointer is at the end: the slow one is in the middle
    return slow.val

How to spot it

Asked: Find the middle of a linked list in one pass

When the fast pointer has covered the whole list, the slow one, at half the speed, has covered half of it.

Asked: Does following the links ever come back to an earlier node?

In a loop the fast pointer cannot leave. It gains one node on the slow one each round until it lands on it.

Asked: The node that is k places before the end

Start one pointer k nodes ahead and move both together. When the leader reaches the end, the other is k behind.

Limits: Walk a chain using only a constant amount of extra memory

Two variables are all it takes. Remembering every node you passed would need memory for the whole chain.

Looks like it, but is not

• The values are in a sorted array and you look for a pair, moving in from both ends. Use Opposing two pointers. Those two positions start at opposite ends and move toward each other. Here both start together and move the same way.
• Extra memory is allowed, and you only need to know whether a value came before. Use Hash set membership. A set of the values seen is the direct way. Two speeds are for when that memory is not allowed.
• You must change the order of the nodes, not only find one node. Use Linked list pointer rewiring. Finding a place changes no link. A new order means pointing links somewhere new.

Cost and mistakes

Time is about n steps for n nodes, written O(n): the fast pointer reaches the end after about half that many rounds. Extra space is two variables, written O(1), however long the chain is.

Watch out

• Before the fast pointer takes two steps, test both fast and fast.next. If you test only one of them, a step can start from nothing and the program stops with an error.
• With an even number of nodes there are two middle nodes, and this loop stops on the second. To stop on the first, continue only while fast.next and fast.next.next both exist.

In the 150

3 problems of the 150 use it. Naming them gives their method away, so the list is folded.