Floyd's Cycle Detection

Task: Find out whether this list loops, using two pointers

The problem

A linked list is a chain. Each node holds a value and points at the next one.
Normally the last node points at nothing, so if you keep walking you eventually stop.
But what if some node points back to an earlier one?
Then walking never ends. You go round and round, forever.

So the question is simple: does this list loop?

This matters more than it sounds. A loop in a list is a bug that does not crash anything: your code just hangs. Something has to notice, and noticing is harder than it looks.

The obvious idea, and why it costs

The first thing most people think of is to remember every node you have seen.

Walk the list. At each node, ask "have I been here before?" If yes, there is a loop. If you reach the end, there is not.

That works. It also means keeping a note of every single node, so a list of a million nodes needs a million notes.

Remember everything

Works, but the memory it needs grows with the list. A million nodes, a million notes.

Floyd's

Works, and needs room for exactly two pointers. It does not matter how long the list is.

That is the whole appeal. Same answer, no notebook.

The idea

Put two pointers at the start of the list.

Move the slow one forward one node at a time.

Move the fast one forward two nodes at a time.

If they ever land on the same node, the list has a loop. If the fast one reaches the end, it does not.

That is the entire algorithm. Two pointers and different speeds.

The reason it works has nothing to do with lists. It is about shapes.

Picture two runners on a straight road, one twice as fast. They never meet: the fast one just gets further ahead, and the gap grows forever.

Now put them on a circular track. The fast one pulls ahead, comes all the way round, and arrives behind the slow one. Then it catches up.

A loop is a circular track. That is why the fast pointer catches the slow one.

Watch it happen

The animation at the top of this page runs it on a seven node list whose last node points back to the fourth. Here it is as numbers.

Slow walks 1, 2, 3, 4, 5. Fast walks 1, 3, 5, 7, and then round the loop back to 5.

Notice that fast was on node 5 in round two and slow did not get there until round four. They did not meet then, because they were not there at the same time. Meeting means being on the same node in the same round.

But could fast jump over slow?

This is the question worth asking, and it is where most explanations stop early.

Once both pointers are inside the loop, think about the gap between them: how many nodes fast would have to walk to reach slow.

Each round, slow moves forward one and fast moves forward two. So fast gains one node on slow. Every round. Without fail.

A number that goes down by one each time cannot skip a value. It cannot jump from 1 straight to −1. It has to pass through 0.

And a gap of zero means both pointers are standing on the same node.

Fast gains exactly one node per round, so the gap shrinks one at a time and must hit zero. That is why the two pointers are guaranteed to meet, not just likely to.

Try it

Press step to run one round. Press no cycle to cut the loop and watch the same list end instead.

Try it yourself

One step against two, until they meet or the list runs out

slow = fast = headboth pointers start at the head

round 0 · ready

Running it both ways is worth doing. Seeing them meet shows that they can. Seeing the fast pointer walk off the end of a straight list shows that meeting actually means something.

The code

CodeFloyd's cycle detection

def has_cycle(head):  slow = head  fast = head   while fast is not None and fast.next is not None:      slow = slow.next          # one step      fast = fast.next.next     # two steps       if slow is fast:          return True           # they met, so there is a loop   return False                  # fast ran out of list

Two things to notice.

The while checks both fast and fast.next. If you only check one, fast.next.next will blow up the moment the list ends.

The comparison is slow is fast, not slow.value == fast.value. Two different nodes can hold the same number. What matters is whether they are the same node.

Watch out

Do not check slow is fast before moving them. Both start at the head, so they are already equal, and the function would report a loop on every list you gave it.

What it costs

Cost	Time	Space	Why
Time	O(n)	—	Each pointer walks the list at most a couple of times.
Space	—	O(1)	Two pointers, whatever the list size.

The space is the point. Remembering every node also finds the loop, but this finds it with two variables.

A list has 5 nodes and the last one points back to the very first.

Is there a loop?
Roughly how many rounds before the pointers meet?

Show answer

Yes. The last node pointing back to the first makes the whole list one big loop.
Both pointers are inside the loop from the start, and the gap grows by one each round until it wraps. With 5 nodes they meet within 5 rounds. You do not need the exact number, only that it is bounded by the size of the loop.

Quick recap

Two pointers, both starting at the head
Slow moves one node, fast moves two
If fast reaches the end, there is no loop
If they land on the same node, there is
It needs no extra memory, however long the list is

Floyd's cycle detection finds a loop with two pointers moving at different speeds. On a loop the faster one always comes round behind the slower one and catches it, so meeting is proof that the list cycles.