How to find the loop in singly linked list

If we are having the singly linked list then last node of the list is linked with middle (or) any node in the list then it causes the loop then how to find the loop with less time complexity

Showing Answers 1 - 2 of 2 Answers

prasanjeet

  • Aug 25th, 2011
 

Take 2 pointers (say p & q) pointing to the start of the list. Increment p by one and q by 2 till p and q points to the same node (in case of loop) or one of them reaches the end (in case of no loop).

  Was this answer useful?  Yes

Method 1.check the node pointed to by the outer loop, with every node of the inner loop.

Method2. Have a visited flag in each node of the linked list. Flag it as visited when you reach the node. When you reach a node and the flag is already flagged as visited, then you know there is a loop in the linked list.

Method3. Have 2 pointers to start of the linked list. Increment one pointer by 1 node and the other by 2 nodes. If there's a loop, the 2nd pointer will meet the 1st pointer somewhere. If it does, then you know there's one.

Code for method 3 is as follows:

Code
  1. p=head;

  2. q=head->next;

  3.  while(p!=NULL && q!=NULL)

  4. {

  5.  if(p==q)

  6. {

  7. //Loop is there

  8. exit(0);

  9. }

  10. p=p->next;

  11. q=(q->next)?(q->next->next):q->next;

  12. }

  13.  

  14. // there is no loop

  Was this answer useful?  Yes

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

 

Related Answered Questions

 

Related Open Questions