Detect Loop in a Linked List

Existence of loop/cycles in a linked list means that last node points to one of the existing nodes of the list instead of pointing to null. So normal approach of traversing the list until you find null will NOT work here. This is one of the most interesting and tricky problems of Linked List. In below sample; next pointer of Node 5, points to Node 3.

                                              1 -> 2 -> 3 -> 4 -> 5 -> 3

This is solved by the famous Tortoise and Hare Algorithm; also known as Floyd algorithm. I wanted to write this article on same, but dropped plan after finding few nicely written posts. So, in this post, I will be explaining an alternative and much easier solution to detect the cycle in a linked list.

Detect Using Map

Tortoise and Hare algorithm uses two pointers (slow and fast); these pointers traverse the list in such a way that fast runs twice as fast as the slower pointer. So, if both these pointers meet at some node; then it means there is a cycle/loop. This approach basically checks if a node points to an already traversed node (5 points to 3 in above example). 

An alternative approach is quite trivial compared to the normal approach but; it has some space overhead. Loop can be identified by storing nodes in a Map. And before putting the node; check if the node already exists. If the node already exists in the map then it means that Linked List has a loop.

Below method detects the loop. I have not given full source code of the linked list. You can get it from my earlier post here.

 public boolean loopDetector(Node<E> first) {  
           Node<E> t = first;  
           Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();  
           while (t != null) {  
                if (map.containsKey(t)) {  
                     System.out.println(" duplicate Node is --" + t  
                               + " having value :" + t.data);  
   
                     return true;  
                } else {  
                     map.put(t, t);  
                }  
                t = t.next;  
           }  
           return false;  
      }  

To test it, make sure that you create a linked list with a loop. To create a loop you need to refactor add method to take next reference as well. So in case of the cycle next reference will point to an existing node instead of pointing to null.
obj.add(item, previousNode);

Note here that, I have used, IdentityHashMap [Java Doc] implementation of Java. Instead of object equality, IdentityHashMap uses reference equality. It considers two keys k1 and k2 equal if and only if (k1==k2). So this map fits aptly in our case to check if the node is already added.