Leetcode Problem 142 : Linked List Cycle II solution

Given a linked list containing a loop, find the start node of the loop.

This is an interesting question asked in many technical programming interviews. The slow ptr — fast ptr solution to the problem of detecting a loop in a linked list can be extended to get a solution of this problem.

Algorithm

1. Start with two pointers slow_ptr and fast_ptr. Initialize both to the head of the linked list.
2. Move slow_ptr to the next node in the list and move fast_ptr to the next-to-next node.
3. Check if slow_ptr and fast_ptr point to the same node.
4. Repeat steps 2 and 3 above until step 3 becomes true. Since it is given that the linked list contains a loop, the two pointers will meet eventually at some node in the loop.
5. Keep one of these pointers, say slow_ptr, at the meeting point. Move the other pointer, fast_ptr here, to the start of the linked list.
6. Move slow_ptr to the next node and move fast_ptr to the next node.
7. Check if slow_ptr and fast_ptr point to the same node.
8. Repeat steps 6 and 7 above until step 7 becomes true. The node pointed to by both the pointers is the start node of the loop.

Lets see why steps 6–8 will work.

In the figure shown above, A is the start of the linked list, B is the point where the two pointers meet after performing steps 2–4, O is the start node we want to find, x is the distance between A and O, y is the distance between O and B, and L is the loop length.

Suppose, when the two pointer meet at B, d_f and d_s are the distances traveled by the fast and slow pointers respectively. Its clear that:

d_f = x + n1*L + y, where n1 is some integer value. (1)
d_s = x + n2*L + y, where n2 is some integer value (2)

n1 >= n2 always holds.

Also, since fast pointer moves at double the speed of slow pointer, we have,

d_f = 2*d_s (3)
Substituting (1) and (2) in (3), we get,

x + n1*L + y = 2*x + 2*n2*L + 2*y
x = (2*n2 — n1)*L — y
x = n*L — y, where n = 2*n2 — n1 (4)

From (4), we can see why moving fast_ptr from the beginning (A here) and slow_ptr from the meeting point (B here) at the same pace, will cause the pointers to meet at the start node of the loop (O here).

Originally published at http://kamaljeet-verma.blogspot.com on July 5, 2012.