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.

Find middle node of a LinkedList

Finding the middle node of a linked list by traversing the list twice is trivial. But what makes this problem interesting is; If you have to do this in a single pass/traversal. 

Here, I will be using Java to solve this problem. Java provides a built-in API LinkedList, so using inbuilt iterator and size method of this API, the middle element can be easily found. But that would defy the whole intention behind this problem. Better do it more crude way! 

In Linked List post, I have created a custom single linked list. I am reusing the same class here, and have added a new method/s to find the middle node.

Find Middle Node

Approach to find the middle node is: keep two references, one pointing to middle and other pointing to end of the list. Keep on traversing the list and make sure that middle reference always points to the middle node at any point of traversal. Done!!!

package algo;  
 /**  
  * Generic single linked list implementation with generics  
  *   
  * @author Siddheshwar  
  *   
  */  
 public class SingleLinkedList<E> {  
      Node<E> start; // points to the head or first node  
      /**  
       * Node class  
       */  
      private static class Node<E> {  
           E data;  
           Node<E> next;  
           public Node(E data, Node<E> next) {  
                this.data = data;  
                this.next = next;  
           }  
           public E getData() {  
                return data;  
           }  
           public Node<E> getNext() {  
                return next;  
           }  
           public void setNext(Node<E> next) {  
                this.next = next;  
           }  
      }  
      public void add(E d) {
           if (start == null) {  
                start = new Node<E>(d, null);  
           } else {  
                Node<E> tmp = start;  
                while (tmp.getNext() != null) {  
                     tmp = tmp.getNext();  
                }  
                tmp.setNext(new Node<E>(d, null));   // add at the end of list  
           }  
      }  
      public void print() {  
           Node<E> current = start;  
           System.out.print(" values in link-list are :");  
           while (current != null) {  
                System.out.print(current.getData() + "--> ");  
                current = current.getNext();  
           }  
           System.out.println("null");  
      }  
      /**  
       * Finds middle object/node of linked list  
       * Approach : increment middle node alternate time 

       * (i.e. when count is odd)  
       */  
      public Node<E> findMiddleNode(Node<E> start) {  
           if (start == null)  
                return null;  
           Node<Integer> end = (Node<Integer>) start;  
           Node<Integer> middle = (Node<Integer>) start;  
           int count = 0;  
           while (end != null) {  
                end = end.getNext();  
                // move middle pointer alternate times  
                if (count % 2 == 1) {  
                     middle = middle.getNext();  
                }  
                count++;  
           }  
           return (Node<E>) middle;  
      }  
      /**  
       * Find middle node - Alternate approach 
       *   
       */  
      public Node<E> middleNode(Node<E> start) {  
           if (start == null)  
                return null;  
           Node<Integer> end = (Node<Integer>) start;  
           Node<Integer> middle = (Node<Integer>) start;  
           while (end != null) {  
                end = end.getNext();  
                if (end != null) {  
                     end = end.getNext();  
                     middle = middle.getNext();  
                }  
           }  
           return (Node<E>) middle;  
      }  
      public static void main(String[] args) {  
           SingleLinkedList<Integer> sll = new SingleLinkedList<>();  
           sll.add(1);  
           sll.add(2);  
           sll.add(3);  
           sll.add(4);  
           sll.add(5);  
           sll.add(6);  
           sll.add(7);  
           sll.print();  
           Node<Integer> middle = sll.middleNode(sll.start);  
           System.out.println("Middle value --:" + middle.getData());  
           middle = sll.findMiddleNode(sll.start);  
           System.out.println("Middle value --:" + middle.getData());  
      }  
 } 

Output:

 values in link-list are :1--> 2--> 3--> 4--> 5--> 6--> 7--> null
Middle value --:4
Middle value --:4

Note that there are two methods to find the middle node; both are more or less same, though.

Complexity:
End reference traverses the list fully once (i.e. O(n) ) and middle reference traverses only till the middle of the list (i.e. n/2 nodes / O(n)). Summing up those two still makes its complexity as O(n).

You can use this approach to solve similar problems:

• Find the nth node from the last.
• Remove the middle node of the list. 
• Pairwise swapping of nodes (1->2->3->4 becomes 2->1->4->3)
• Split a linked list in 2 ( or 3) equal  or close to equal linked list
• Delete the repeated elements from a linked list.
• Append last n nodes of the list to the beginning.