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:

Data Structure

Tagged in:

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