Sunday, 22 May 2016

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 */ = start;

      /** Move the start to point to new Node */
      start = nNode;

   int detectLoop() {
      Node pSlow = start;
      Node pFast = start;
      while (pSlow != null && pFast != null && != null) {
         pSlow =;
         pFast =;
         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();


      /** Create loop to test. */ = list.start;


No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...