Friday, July 10, 2015

Finding the beginning of a loop in a link list.

Let's jump right into it.

I uploaded the drawings I made while trying to understand the algorithm. Just some rough sketches, thought it'd be handy.

4 steps.

Step 1: Assign two pointer to the head of the link list.

Slowpointer-Traverse 1 step at a time

Fastpointer- Traverse 2 steps at a time.


As you see here, both the f and s pointer are at the head of the link list.

Step 2: By the time the slow pointer has entered the loop, the fast pointer will be at k steps into the loop.


As you see here, s is at the beginning of the loop (position 0) and f is at k steps into the loop (3)

Step 3: Now both the pointers will collide at a single location after (length of loop-k) steps


Here the length of the loop is 5. And k was 3. So after traversing the s and f pointers 2 more times with their respective speeds they'll collide at the point show in figure. This point is k steps away from the head of the loop.

Step 4: Move your slow pointer to the head of the link list and start traversing both pointers with a speed of 1. The next time they'll collide, will be at the head of the loop. Ta-da! you're done.




Here, after f and s move 3 more times with a speed of 1, they'll collide at the head of the loop!

No comments:

Post a Comment