IDK IDK - 18 days ago 9
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

fast.next == slow
we are done.
The code would look something like this

slow = head;
fast = head.next;

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

return fast; /* The starting loop node*/


Edits: I meant fast.next != slow

Answer

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)