How to detect a loop in a linked list? Write a C program to detect a loop in a linked list.
Filed under: Computer Science Interview Questions, Linked List Interview Questions
Brute force method
Have a double loop, where you check the node pointed to by the outer loop, with every node of the inner loop.
typedef struct node
{
void *data;
struct node *next;
}mynode;
mynode * find_loop(NODE * head)
{
mynode *current = head;
while(current->next != NULL)
{
mynode *temp = head;
while(temp->next != NULL && temp != current)
{
if(current->next == temp)
{
printf(“\nFound a loop.”);
return current;
}
temp = temp->next;
}
current = current->next;
}
return NULL;
}
Visited flag
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.
Fastest method
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.