Wednesday, October 31, 2012

Problem 3: Detect a loop and delete in Linked List

Problem 3: Detect a loop and delete in Linked List.

Solution: There will be two task to solve the issue.
  1. To check whether there is any loop in the linked list, if not then there is nothing to do.
  2. If loop is found in Step 1 then we have to remove that.
Find the loop in linked list:
  1. Take two pointers p1 and p2, where p1 -> head of the list and p2 -> next element after head.
  2. Increment p1 by one every iteration and p2 by two.
  3. And after each iteration check whether they are pointing to same memory if so then there is a loop.
  4. In case there is no loop then p1 will reach at end and there is nothing to solve.
Now let's consider we found the loop:
The above algo will work as following iteration:

So now p1 and p2 is pointing to D and we found a loop.
By doing this we are sure that D is definitely part of the loop elements.

Delete the loop in the linked list:
     1. Find the number of elements which are part of the loop, in the above case count will be 4 as follows:
           a) Keep p1 at D only and reset p2 to head.
           b) Increment p2 by one till it reaches to p1 (i.e. D)
           c) Number of increment done will be the count of elements in the loop

     2. Now we know that there is a loop in the list and the number of elements present in the loop. The faulty node( where the loop exists i.e. F) can be founded by following steps:
           a) Keep p1 at head and p2 at head + count.
           b) Increment both p1 and p2 at same pace, the moment when p2 equal to p1 stop there.
           c) Node visited before p2 is the faulty node.

No comments:

Post a Comment