Two pointers at different speeds

One pointer moving twice as fast finds the middle, and catches anything going in circles.

Key idea

Finding the middle in one pass

You cannot index into a linked list, so finding the middle looks like it needs two passes: one to count, one to walk halfway.

It does not. Move one pointer one step at a time and another two steps at a time. When the fast one reaches the end, the slow one has covered exactly half the distance and is standing on the middle.

1class Node:2    def __init__(self, val, next=None):3        self.val, self.next = val, next4 5def build(values):6    head = None7    for value in reversed(values):8        head = Node(value, head)9    return head10 11def to_list(node):12    out = []13    while node:14        out.append(node.val)15        node = node.next16    return out17 18def middle(head):19    slow = fast = head20    while fast and fast.next:21        slow = slow.next22        fast = fast.next.next23    return slow24 25print(middle(build([1, 2, 3, 4, 5])).val)26print(middle(build([1, 2, 3, 4])).val)

Why it works

Why a fast pointer catches a cycle

If the list loops back on itself, the fast pointer enters the loop first and then goes round it. The slow pointer arrives later and also goes round.

Once both are inside, the fast pointer gains exactly one position on the slow pointer per step. A gap that shrinks by one every step and can never skip a value must eventually reach zero, so they meet. If there is no cycle, the fast pointer simply reaches the end.

That one-per-step argument is the whole proof, and it is why the speeds are one and two rather than any other pair. A faster pointer would close the gap by more than one per step and could jump over the slow pointer without ever landing on it.

Nothing about that argument needs a linked list. Below, two runners sit on six numbered positions arranged in a loop, and the printed value is the distance the fast one still has to close.

1# Six positions in a loop. Slow advances 1 place per step, fast advances 2.2slow, fast = 0, 43print((slow - fast) % 6)4 5for _ in range(2):6    slow = (slow + 1) % 67    fast = (fast + 2) % 68    print((slow - fast) % 6)

The gap fast still has to close, measured forward around the loop.

Trace it· 8 min

Trace fast and slow

Run the middle-finding loop on a five-node list holding 1 through 5. For each pass give the values slow and fast are standing on after the step, writing None when a pointer has run off the end.

pass	slow	fast
1
2

Problem· 18 min

Linked List Cycle

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1class Node:2 def __init__(self, val, next=None):3 self.val, self.next = val, next4 5def build(values):6 head = None7 for value in reversed(values):8 head = Node(value, head)9 return head10 11def to_list(node):12 out = []13 while node:14 out.append(node.val)15 node = node.next16 return out17 18def middle(head):19 slow = fast = head20 while fast and fast.next:21 slow = slow.next22 fast = fast.next.next23 return slow24 25print(middle(build([1, 2, 3, 4, 5])).val)26print(middle(build([1, 2, 3, 4])).val)

1# Six positions in a loop. Slow advances 1 place per step, fast advances 2.2slow, fast = 0, 43print((slow - fast) % 6)4 5for _ in range(2):6 slow = (slow + 1) % 67 fast = (fast + 2) % 68 print((slow - fast) % 6)

pass

slow

fast