Welcome, %1$s. Please login or register.

December 12, 2017, 12:03:29 PM
: 1
: Loop inside a linked list  ( 3117 )
« : May 12, 2007, 12:15:58 AM From Shrinidhi»



Loop inside a linked list


Given a single linked list, write a program/algorithm to find whether there exists any loop. (Without using any extra memory of O(n))

 
Liked It? Share it!

              


« #1 : May 12, 2007, 12:17:26 AM From Shrinidhi»

1.   Keep 2 pointers. Say p and q.
2.   Make p & q both point the head of the list.
3.   Move p by one node and q by 2 nodes.
4.   Repeat step 3 until
         a.   Either q points to NULL. In this case there is no loop.
         b.   Or Both p & q meet each other again. In this case there is loop.
« #2 : May 12, 2007, 12:18:28 AM From Shrinidhi»

int isLoop(Node *head)
{
Node *p=head;
Node *q=head->next;

while(p!=NULL && q!=NULL)
{
  if(p==q)
  {
     return 1; //Loop Exists. Hence return success
  }
  p=p->next;
  q=(q->next)?(q->next->next):q->next;
}
return 0; //There is no loop
}


« #3 : May 18, 2007, 11:29:28 PM From Prateek»

I was asked in Cisco interview to calculate the worst case and best case time complexity for finding whether there exists a loop.

Can anyone tell me what they are?
« #4 : May 19, 2007, 12:18:54 AM From Poonam»


Node1 -> Node2 -> Node3 -> Node4 -> Node5 -> Node6 -> Node7 -> Node8 -> Node5

This linked list is looping from 8 back to 5. There are 4 nodes before the loop and 4 nodes inside. In this linked list and in the algo as explained by shrinidhi the loop is detected as soon as the pointer p moves to node5 for the first time. And there cannot be any other best scenario possible...
Hence the best case time complexity is node k+1 where k is the number of nodes outside the loop.
« #5 : May 19, 2007, 11:26:12 AM From Ria»

Yeah I agree with Guru... O(k+1) is the best case time taken if there exist a loop.
However if there aren't any loop in the linked list it will be found in just n/2 steps, where n is the number of nodes in the list.
: 1
« previous next »

 

Best RatedList All>>



Latest
Random



SMF 2.0.10 | SMF © 2015, Simple Machines | Contact Webmaster | OnlineFunDb.com © 2009/10 | Legal Disclaimer