# 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

#### 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).

#### Rahul_Sharma Profile Answers by Rahul_Sharma

• Sep 4th, 2011

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:

```Codep=head;
while(p!=NULL && q!=NULL)
{
if(p==q)
{
//Loop is there
exit(0);
}
p=p->next;
q=(q->next)?(q->next->next):q->next;
}

// there is no loop```