Leave a comment

Find the loop in a given Link List. Analyze the complexity of solution.

Link list is one of those data structures on which you can find a lot of stuff on internet. From a very simple problem to a complex one. Here in this blog also we are going to discuss problems along the same line.
Continuing in the same direction, let’s discuss our first problem. Suppose you have given a link list and there is a loop in the list. For understanding, you can assume a link list and someone might have modified the next address field (remember the structure of the node of link list?) of its last node and made it pointing to some node in the middle of the list. Got the point? We need to find out if there is a loop in the list. If loop is there, which node is the starting point of loop? (as in below list, 4 is the starting point)

Untitled

Most of the people already know the solution but I would like to discuss one more time to make those people understood who are seeing first time.
Let’s take a general problem where two bikes are running on a rounded path. One bike is running at a speed of 80 kmph and another is running at 50 kmph. They started at the same time from same point. Do you think they will meet at some point again once they started and running continuously? Of course the will meet. Actually, the bike running at a speed of 80 kmph, continuously coming closer to another bike. Both are running in the same direction, so you can assume one bike is standing and another is running at 30 kmph. As the path is rounded, running bike will reach to standing bike sometime. I hope you got it.
Same logic will be applied here. We will take a fast pointer which will jump next to next node from its current position and a slower pointer which will jump next to its current position. We will do the same exercise until we meet the termination condition. Termination condition would be either both the pointer meet or fast pointer cannot jump anymore which means either the next or next to next node of fast pointer is null and in turn says no loop in the list.

Let’s consider the list given above. Let’s take two pointer P1 and P2. P1 is slower and P2 is faster. Initially both pointing to the head of the list which is 1. Now, P1 will jump next to it and reach at 2 and P2 will jump next to next to its current position and will reach at 3. Following the same approach rest of the iteration will be as follows:

  1. P1 => 3, P2 => 5
  2. P1 => 4, P2 => 7
  3. P1 => 5, P2 => 9
  4. P1 => 6, P2 => 11
  5. P1 => 7, P2 => 5
  6. P1 => 8, P2 => 7
  7. P1 => 9, P2 => 9

So, we reached at the termination condition. Once they met, we found that loop exists.
Now, another problem is to find the starting point of the loop. Let’s think about it. One way of doing this, check if next of the current node is pointing to any of the previous node in the list. If so next node of the current node is starting point in loop. This will definitely hit the performance as each time you need to visit all the previous nodes to current node and check if anyone is next to current node.
Let’s find a fast solution to find the starting point. If we could find total number of nodes in loop, we can put a pointer forward by that many number from first node and another pointer pointing to first node. Now, both will jump to next node from the current position until they meet. Meeting point will be the starting point as one node is already forward by that many number of nodes which exist in loop. As we are forwarding a pointer by size of the loop that means the distance between both the pointer will be same as size of the loop so, when first pointer will reach at starting node in loop, second pointer will also be at same node as it is continuously maintaining the distance equals to the size of the loop from first node.
Now to find out the size of the loop, once both the pointer meet while checking if loop exists in list, we will keep pointer P1 static on the meeting point and P2 will keep moving but now it will be jumping to its next node only until it meets P1 again. The total number of jumps are the number of nodes exist in the loop so the size of the loop.
Note: This solution is taken from book “Cracking the coding Interview”. Slight changes are there.

I am not going into the implementation. Please find the algorithm herein below:

  1. Let’s say “head” is the head of the given list
  2. P1 = head, P2 = head
  3. while ((P1 != P2 after head node) && (p2 has its next exist && p2 has its next to next exist))
    p1 = p1->next
    p2 =p2->next->next
  4. if(p2 has no next || p2 has no next of next) “no loop in list”. exit.
  5. p2 = p2->next
  6. count = 1
  7. while( p2 != p1)
    p2 = p2->next
    count++
  8. P1 = head, set P2 forward by count number of nodes from P1
  9. while(P1 =! P2)
    P1 = P1->next
    P2 = P2->next
  10. P1 and P2 are at starting point in loop.

Please let me know If code is required.

Complexity Analysis:
So first thing is why we have chosen that fast pointer will jump on 2nd node and not 3rd node. While trying to find out loop in list, might it happen that fast pointer will jump over slow pointer and you do not find loop till infinite?

So here is your answer, you must have observed that one pointer is jumping by one node and other by two node in same direction, so the difference of speed in these two pointer is one. We can assume that slower pointer is static and pointing to some node in loop and fast pointer is moving by 1 node each time. So it will never ever jump over the slow pointer and in single iteration both the pointer will meet.
At maximum, slower pointer will have to visit all the node before fast pointer catches it. So the complexity would be O(n) where n is total number of nodes in list.

We can calculate the complexity to find out the starting point in the loop as follows:
Complexity can be broken in sub problems: complexity to find if loop exist (we will get the meeting point of two pointers) + complexity to find the size of loop + complexity to find the meeting point of two pointers where one pointer is kept forwarded by size of the loop (need to visit all the nodes)
Let say size of the loop is m.
Complexity => O(n) +O(m)+ O(n) => O(n)

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

%d bloggers like this: