Fast and slow pointers

Two names walk along the same list at different speeds. The gap between them tells you things that one walk alone cannot: where the middle is, and whether the list goes round in a loop.

The middle node

To find the middle node, you could count the nodes, then walk half that many. That is two walks. With two names you need only one: slow moves one node per pass and fast moves two. When fast reaches the end, slow has gone half as far.

slow = fast = head
while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next
return slow

The loop checks fast.next as well as fast, because fast takes two steps at once and must not step off the end. With an even number of nodes, slow stops on the second of the two middle nodes. To stop on the first, start fast at head.next.

Does the list have a loop?

A bug, or bad input, can make a list’s last node point back to an earlier node. Then the list has a loop (also called a cycle), and a walk that waits for None never ends. How can you tell, without storing every node you have seen?

Run slow and fast as before. If there is no loop, fast reaches None. If there is a loop, both names end up going round it, and fast catches slow from behind. Switch the figure to “Find a loop” to watch.

slow = fast = head
while fast is not None and fast.next is not None:
    slow, fast = slow.next, fast.next.next
    if slow is fast:
        return True      # they met: there is a loop
return False             # fast reached the end: no loop

Why must they meet, and not jump past each other? Once both are in the loop, look at how many nodes fast is behind slow. Each pass, slow moves 1 and fast moves 2, so the gap shrinks by exactly 1. A gap that shrinks by 1 each time cannot skip over 0. It reaches 0 within one trip round the loop.

So the number of passes is at most the number of nodes before the loop, plus the loop’s length: O(n) time. Only two names are stored: O(1) space. Storing every visited node in a set also works in O(n) time, but needs O(n) space. This method is known as Floyd’s cycle detection, after Robert Floyd.

Where the loop starts

After they meet, put a new name p at the head. Move p and slow one node at a time. They meet exactly at the first node of the loop.

Here is why. Call the number of nodes before the loop a, and the length of the loop L.

• When the two names met, slow had taken some number of steps, call it s. fast had taken 2s, twice as many.
• fast took s more steps than slow and ended on the same node. Those extra steps were whole trips round the loop. So s is a whole number of loop lengths: s = kL, which means k times L, for some whole number k.
• Now p walks a steps from the head and arrives at the loop’s first node. In the same time, slow has taken s + a steps in total. That is a steps to reach the loop, plus kL steps, which is whole trips round it. So slow is also at the loop’s first node.

So the code has two parts. The first is the meeting loop from above. When slow is fast, start the second part: put p at the head, and move p and slow one node at a time while p is not slow. Where they stop is the first node of the loop. If fast reaches the end instead, there is no loop. LINK-P5 asks you to write both parts.

A fixed gap: k-th from the end

The two names can also keep a fixed gap instead of different speeds. To find the k-th node from the end in one walk, move fast k nodes ahead first. Then move both one node at a time. When fast reaches None, slow is k nodes from the end.

Now try LINK-P5, Where the loop starts.