Detect Loop in Linked List: Data Structure

Detect the Loop in Linked List: In this problem, we will be seeing some technique through which we can detect the loop in linked list. We will discuss each technique one by one.

Technique 1: Hashing method: -

In hashing method, we traverse the list one by one and we put the addresses of the node in a hash map. At any point, if we get NULL then we return false and if next of present or current node is found in hash map then we will return true.

//Implementation of above method in Java Language 
import java.util.*;
 public class ListLoopDetection {
     static Node start;  
     /* Linked list Node*/
     static class Node {
         int data;
         Node next;
         Node(int d)
         {
             data = d;
             next = null;
         }
     }
     /* Inserts a new Node into the linked list */
     static public void add(int new_data)
     {
         Node node = new Node(new_data);
          node.next = start;
         start = node;
     }
     // Function returns true if loop is in linked list
     //Else returns false.
     static boolean detectLoop(Node h)
     {
         HashMap<Node,Boolean> s = new HashMap<Node,Boolean>();
         while (h != null) {
             if (s.get(h) != null)
                 return true;
             s.put(h,true);
             h = h.next;
         }
         return false;
     }
     /* Driver function for checking the program */
     public static void main(String[] args)
     {
         LinkedList ll = new LinkedList();
         ll.add(20);
         ll.add(4);
         ll.add(15);
         ll.add(10);
         /*Create loop for testing */
         ll.start.next.next.next.next = ll.start;
         if (detectLoop(start))
             System.out.println("Loop found");
         else
             System.out.println("No Loop found");
     }
 } 

Output: -

Loop found

Complexity Analysis: -

The time complexity of this solution is O(n) and the space complexity of is O(n).

Technique 2: Floyd’s Cycle-Finding Algorithm: -This method is faster than above, in this we traverse the whole linked list using two pointers. We move the one pointer by next called slow pointer and another pointer by next to next called fast pointer. Then we will check if these two pointers meet at the same node then we can say there is a loop present in the linked list and these pointers don’t meet to each other then we can say the linked list doesn’t contain any loop.

 //Implementation of above method in C Language
 #include <stdio.h>
 #include <stdlib.h>
 /* Link list node */
 struct Node {
     int data;
     struct Node* next;
 };
 void add(struct Node** ref, int new_data)
 {
     /* allocate node */
     struct Node* node = (struct Node*)malloc(sizeof(struct Node));
     node->data = new_data;
     node->next = (*ref);
     (*ref) = 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) {
             return 1;
         }
     }
     return 0;
 }
 /* Driver function for checking the program */
 int main()
 {
     /* Start with the empty list */
     struct Node* start = NULL;
     add(&start, 20);
     add(&start, 4);
     add(&start, 15);
     add(&start, 10);
     /* Create a loop for testing */
     start->next->next->next->next = start;
     if (detectLoop(start))
         printf("Loop found");
     else
         printf("No Loop found");
     return 0;
 } 

Output: -

Loop found

Complexity Analysis: -

The time complexity of this solution is O(n) and the space complexity of is O(1).