Detect loop in a linked list ?



Detect loop in a linked list ?

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

    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
            


            Related Searches to