CODEWITHSUNDEEP
javalinked-list
Hooli
Hooli

Reputation: 731

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

Upvotes: 0

Views: 607

Answers (1)

palako
palako

Reputation: 3470

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)

Upvotes: 3

Related Questions