Amazon.com

www.amazon.com

Interview Question

Software Engineer Interview

Length of a circular linked list

Answer

Interview Answer

1 Answer

0

Let's take 2 pointers: first steps with step=1, second steps with step=2. If pointers meet, therefore there is a loop in a linked list.

Statement: two pointers will meet in N steps.

Indeed, let's imagine that such point is J. First pointer stepped J times, while second point stepped 2*J times, moreover, second pointer made additional k*N circles to J, i.e J+kN.

2*J = J+kN, means J = kN, i.e. J is a multiple of N. Now there is need to demonstrate that k = 1. It can be proved by induction.

Tim on Feb 1, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.