IDK IDK - 1 year ago 99
Java Question

Why does the fast pointer in loop detection of linked list need to be two steps ahead?

Most of the solutions for detecting the loop in a linked list say that the fast pointer need to move twice the steps of the slow pointer. Why can't we have the fast pointer be just one step ahead and if == slow
we are done.
The code would look something like this

slow = head;
fast =;

while( != slow)
slow =;
fast =;
if(fast == null) /* No loop to begin with, break */

return fast; /* The starting loop node*/

Edits: I meant != slow

Answer Source

First, because your pointers will never meet, since fast will always be one ahead of slow, and the pointers meeting is what you use to detect a cycle.

Also, if you do have loops, you will get into infinite loops. Let's say you have

1 -> 2 -> 3 -> 4
  1. when slow is 1, fast is 2
  2. when slow is 2, fast is 3
  3. when slow is 3, fast is 4
  4. when slow is 4, fast is 2
  5. when slow is 2, fast is 3 (we've been here before, infinite loop)
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download