Detect loop in a linked list ?

  • There are two ways to detect loop in linked list or not.
 Detect Loop in a Linked List

Method 1:

  • Traverse through each node till end , tracking visited node using Hash map.
  • If you find node that is already visited, then there is a loop in LinkedList
  • If you reach till end while traversing then there is no loop in LinkedList
using namespace std; 

struct Node
{
int data;
struct Node* next;
};

void push(struct Node** head_ref, int new_data)
{

struct Node* new_node = new Node;


new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

// Returns true if there is a loop in linked list
// else returns false.
bool detectLoop(struct Node *h)
{
unordered_set<Node *> s;
while (h != NULL)
{
// If this node is already present
// in hashmap it means there is a cycle
// (Because you we encountering the
// node for the second time).
if (s.find(h) != s.end())
return true;

// If we are seeing the node for
// the first time, insert it in hash
s.insert(h);

h = h->next;
}

return false;
}

/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;

push(&head, 21);
push(&head, 14);
push(&head, 5);
push(&head, 10);

/* Create a loop for testing */
head->next->next->next->next = head;

if (detectLoop(head))
cout << "Loop found";
else
cout << "No Loop";

return 0;
}

Output:

Loop found

Method 2:

  • Efficient approach for this problem would be Floyd’s cycle detection algorithm, so steps for this algorithm would be:
    • Use two pointer fastPtr and slowPtr and initialize both to head of linkedlist
    • Move fastPtr by two nodes and slowPtr by one node in each iteration.
    • If fastPtr and slowPtr meet at some iteration , then there is a loop in linkedlist.
    • If fastPtr reaches to the end of linkedlist without meeting slow pointer then there is no loop in linkedlist (i.e fastPtr->next or fastPtr->next->next become null).
// C program to detect loop in a linked list 
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};

void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

int detectloop(struct Node *list)
{
struct Node *slow_p = list, *fast_p = list;

while (slow_p && fast_p && fast_p->next )
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (slow_p == fast_p)
{
printf("Found Loop");
return 1;
}
}
return 0;
}

/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;

push(&head, 10);
push(&head, 4);
push(&head, 5);
push(&head, 10);

/* Create a loop for testing */
head->next->next->next->next = head;
detectloop(head);

return 0;
}

Output:

Found Loop

Categorized in:

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,