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.
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