Program to detect loop in a linked list in Java

Use Hashing:

Traverse the list one by one and keep putting the node addresses in a Hash Map. If next of current node points to any of the previously stored nodes in HashMap then return true.

Mark Visited Nodes:

This solution requires modifications to basic linked list data structure.  Have a visited flag with each node.  Traverse the linked list and keep marking visited nodes.  If you see a visited node again then there is a loop.

Floyd’s Cycle-Finding Algorithm - fastest method:

Traverse linked list using two pointers.  Move one pointer by one and other pointer by two.  If these pointers meet at some node then there is a loop.  If pointers do not meet then linked list doesn’t have loop.

Java code for Floyd’s Cycle-Finding Algorithm:

class LinkedList1 {

   Node start;

   /* Node - data & pointer for next node. */

   class Node {

      int data;

      Node next;

      Node(int d) {

         data = d; next = null;

      }

   }

   /* Inserts a new Node at start of list. */

   public void push(int value) {

      Node nNode = new Node(value);

      /** Make next of new Node as start */

      nNode.next = start;

      /** Move the start to point to new Node */

      start = nNode;

   }

   int detectLoop() {

      Node pSlow = start;

      Node pFast = start;

      while (pSlow != null && pFast != null && pFast.next != null) {

         pSlow = pSlow.next;

         pFast = pFast.next.next;

         if (pSlow == pFast) {

            System.out.println("Found loop in list");

            return 1;

         }

      }

      return 0;

   }

}

public class DetectLoopTest {

   public static void main(String args[])  {

      LinkedList1 list = new LinkedList1();

      list.push(10);

      list.push(40);

      list.push(12);

      list.push(13);

      /** Create loop to test. */

      list.start.next.next.next.next = list.start;

      list.detectLoop();

   }

}