To find out whether your single linked list is circluar 2

Problem is : How to find out whether your single linked list is circluar.

Lets have a look on the “The Tortoise and the Hare Algorithm”.

Time Complexity :  O(n)
Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator) or there will be one slow pointer and one will be fast pointer.
If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle.

So we want to do exactly this thing : p1 = p1-> next and p2 will two steps i.e. p2= p2->next->next

Below is the Java Program for this:
package com.algo.circular.linkedlist;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class FindCircleInLinkedList {
 public static final List<Integer> listOne = new LinkedList<Integer>(){
 {
  add(1);
  add(2);
  add(3);
  add(7);
  add(8);
  add(9);
  add(4);
  add(3); // circlular linked list
  add(7);
  add(8);
  add(9);
  add(4);

}
};

public static boolean isCircularLinkedList(){
 // lets open slow and fast pointer
 Iterator<Integer> slowIterator = listOne.iterator();
 Iterator<Integer> fastIterator = listOne.iterator();

 int slowVisitNode, fastVisitNode;
 while(true){
  // iterate over slowpointer
  if(slowIterator.hasNext()) slowVisitNode = slowIterator.next(); else return false;
  //iterate twice over fast pointer
  if(fastIterator.hasNext()) fastVisitNode = fastIterator.next(); else return false;
  if(fastIterator.hasNext()) fastVisitNode = fastIterator.next(); else return false;

  // now check whether two node are the same one
  if(slowVisitNode == fastVisitNode)
  return true;
 }
}

public static void main(String[] args) {
 System.out.println(isCircularLinkedList());
 }
}

2 thoughts on “To find out whether your single linked list is circluar

  1. Reply SRR Aug 12,2013 1:11 pm

    Have you ever checked your code? This code does only find cycles if index n+1 is the same as index 2*(n+1) in your list. So the code above finds index 4 (being 8) and index 9 (being 8) but not the circular you commented (index 2 and 7).

  2. Reply oppanblogs Aug 13,2013 8:23 am

    Hi SRR,

    I got your point, my motive was only how to detect a loop in a linked list.

    I know the list i have taken here is not containing any loop, for assumption only i took the list with repeated values to simulate the loop.

    Also the code of fast pointer should be like:

    //iterate twice over fast pointer
    if(fastIterator.hasNext()) fastVisitNode = fastIterator.next(); else return false;
    // now check whether two node are the same one
    if(slowVisitNode == fastVisitNode)
    return true;
    }

    if(fastIterator.hasNext()) fastVisitNode = fastIterator.next(); else return false;
    // now check whether two node are the same one
    if(slowVisitNode == fastVisitNode)
    return true;
    }

    Thanks for your comment. 🙂

Leave a Reply