Loop in Linked List

Hi to all,

This is my first article in this blog. The article briefly describes How to Find a Loop in Linked List and Finding the start of the Loop.

To find the Loop in linked list, we can use Floyd’s Cycle Detection Algorithm. The algorithm is also Tortoise – Hare Algorithm. 

Concepts Behind Floyd’s:

Imagine a circular track and two runners. One runner is twice as fast as the other. Both of them start at same point  ‘P’. The only point they will meet in the circular track again is the start point ‘P’.

If the slow runner starts at “S” and fast runner starts at “K” distance away from the point “S”, then they will meet in the circular track at “K” distance before the start point “S”.

See this diagram for clear understanding,

first

The fast runner ‘F’ is quarter distance ahead of ‘S’.  ‘S’ is the starting point. They both meet quarter distance before the starting point ‘S’.

The point we derive from this is :

If  the faster runner is ‘K’ step ahead of the slow runner at the start of the race, then they meet first at ‘K’ Steps before the starting point.

You can have a better understanding , if u are able to crack this spoj problem .

Algorithm:

Consider a linked list with two pointers namely fast and slow pointers.  Slow pointer moves one step at a time and fast pointer moves two steps at a time. At any instance, if slow pointer has moved ‘n’ steps, then faster has moved ‘2n’ steps. In other words faster pointer is  2n – n=n steps ahead of slow pointer.

Eg: 60 —> 50 —> 40 —> 30 —> 20 —>10 —> 5 —> 2 —>40.

Let us assume the loop in linked list starts at the ‘K’th node (40) in linked list. If the slow pointer from the start (60) node has to move ‘K’ (2) steps to enter into the loop at (40), then fast pointer is ‘K’ steps (2) ahead of slow pointer at (20).

Consider loop as ‘ circular track ‘ and fast and slow pointers as ‘fast and slow runners’. If the fast pointer is ‘K’ steps ahead of slow pointer at the start of the race, then they will meet first  ‘K’ steps behind the start of the race.

In the above example, there is a loop at the node ’40’. When the slow pointer is at ’40’, faster will be two steps away from it (i.e.) ’20’. From the previous discussion, they will meet at ‘K’ nodes before the starting point (i.e.) at node ‘5’. 

Finding the start of the loop:

We are few steps away from finding the start of the loop.

  1. As we saw above, when slow pointer moves ‘K’ steps from the start ‘node'(head of the Linked List), it meets fast pointer ‘K’ steps before the start of the ‘loop'( some arbitrary node in the list and  not necessarily head of the list ).  
  2. From the previous point, fast pointer is ‘K’ steps behind the start of the loop and slow pointer has moved ‘K’ steps from start node to start of the loop.
  3. Therefore, if we move slow pointer to the start node and fast pointer at the meeting point and increment step by step, then both fast pointer and slow pointer meet at ‘start of the loop’ after K steps.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s