How to Detect infinite loop in LinkedList with Example

This is a very common interview question. You are asked that if you have a linked list in which you can traverse only in one direction, and if that linked list has a loop in it, how you will detect it??

Well, if you don’t know the answer then don’t be demoralize. My personal opinion is that these kind of questions does not evaluate the logical thinking of a candidate because problems like this have a very specific answer. Either you know it, or you don’t.

For this specific question, best answer interviewer is looking for is “Floyd's Cycle-Finding Algorithm“. This algorithm suggest a solution in which in stead of only one pointer to traverse through list, you are advised to have two pointers at a time. Both pointers will start from first node of linked list and traverse using next attribute.

The difference lies in the number of nodes which they jump in each step. First node jump to next node each time, where as another node jumps two nodes at a time. First node is called slower node or tortoise, and second faster node is called hare.

Tortoise and hare algorithm

This traversal ensures that if there is a loop in linked link then both the nodes will meet somewhere in their traversal path for sure. It has O(n) complexity.

Lets verify this using a java example code.

I have written a least possible single linked list code for demonstration of this example only.

package com.howtodoinjava.demo.core;   public class SinglyLinkedList {       private Node start;       public void add(Integer i)     {         Node node = new Node(i);         if(start == null)             start = node;         else         {             Node temp = start;             while(temp.next != null)             {                 temp = temp.next;             }             temp.next = node;         }     }       public Node getStart()     {         return start;     }       static class Node     {         Node(Integer i)         {             this.value = i;         }           private Integer value;         private Node next;         public Integer getValue() {             return value;         }         public void setValue(Integer value) {             this.value = value;         }         public Node getNext() {             return next;         }         public void setNext(Node next) {             this.next = next;         }     } }

Now, let test above linked list first without loop and then with loop inside it.

package com.howtodoinjava.demo.core;   public class FindLoopsInLinkedList {     public static void main(String args[]) {           FindLoopsInLinkedList finder = new FindLoopsInLinkedList();           SinglyLinkedList sampleList = new SinglyLinkedList();         // First Insert randomly ten elements in a linked list         for (int i = 0; i < 10; i++) {             sampleList.add(i);         }           System.out.println("Loop Existence : " + finder.doesLoopExist(sampleList));         System.out.println("Loop Existence : " + finder.doesLoopExist(finder.createLoop(sampleList)));     }       public boolean doesLoopExist(SinglyLinkedList listToCheck) {         SinglyLinkedList.Node tortoise = listToCheck.getStart();         SinglyLinkedList.Node hare = listToCheck.getStart();           try {             while (true) {                 tortoise = tortoise.getNext();                 hare = hare.getNext().getNext();                 if (tortoise == hare) {                     return true;                 }             }         } catch (NullPointerException ne) {             return false;         }     }       private SinglyLinkedList createLoop(SinglyLinkedList sampleList) {         sampleList.getStart().getNext().getNext().getNext().setNext(sampleList.getStart().getNext());         return sampleList;     } }

In above program, we have creates a linked list and the we inserted 10 elements in this list. No, when we checked the loop presence in line no. 15 it comes as false.

But, when in line 167, we have created a loop inside linked list result comes as true.

Output of above program is this:

Loop Existence : false            [Line 15]
Loop Existence : true             [Line 16]

As you see, as soon as we insert loop in line no. 16, our algorithm implementation is able to detect it.