Write a program to find cycle or detect loop in a single linked list
The most common and easiest way to find a loop or cycle in a linked list is to have too pointer . Increment the first pointer by one and second pointer by two . If both the pointer of linked list matches then there is a loop in a linked list .
Below code show the way how to achieve or find loop in a linked list
public static boolean hasCycle(Node head) {
Node fast = head;
Node slow = head;
while (true) {
if (fast == null || fast.next == null)
return false;
else if (fast == slow || fast.next == slow)
return true;
else {
fast = fast.next.next;
slow = slow.next;
}
}
}
How to find the middle element of a linked list?
Solution 1 (Uses one slow pointer and one fast pointer). Increment the first pointer by one and increment the second pointer by two. When the second pointer would point to the last element of linked list first pointer would point to the middle element of linked list.
Solution 2 Use counter and save the element of the linked list
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.