16 January 2010

Find Loops in a Singly Linked List in Java

This is a very simple yet efficient program written in Java to find whether a Singly Linked List has loops or not. If you need the SingleLinkedList class, please click this link.
The logic is simple, there will be two pointers one traversing once and the other traversing twice. If at all we get a NullPointerException in the process we can be very sure that there are no loops. In the other case, there is definitely a loop. You may play with it. Dont forget to copy this class.
package dsa.linkedlist;

public class FindLoopsInLinkedList {
 public static void main(String args[]){
  FindLoopsInLinkedList finder = new FindLoopsInLinkedList();
  SinglyLinkedList<Integer> randomList = finder.giveMeALoopedList();
  System.out.println("Loop Existence : "+finder.doesLoopExist(randomList));
 }
 
 public boolean doesLoopExist(SinglyLinkedList<Integer> listToCheck){
  Node<Integer> singleJump = listToCheck.start;
  Node<Integer> doubleJump = listToCheck.start;
  
  try{
   while(true){
    singleJump = singleJump.next;
    doubleJump = doubleJump.next.next;
    if(singleJump == doubleJump){
     return true;
    }
   }
  }catch(NullPointerException ne){
   return false;
  }
 }
 
 private SinglyLinkedList<Integer> giveMeALoopedList(){
  SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
  //First Insert randomly ten elements in a linked list
  for(int i=0;i<9;i++){
   sampleList.add(i);
  }
  //Force the list to have a loop in this fashion
  Node<Integer> lastNode = sampleList.getLast();
  lastNode.next = sampleList.getNodeAt(3);
  return sampleList;
 }
}
//-------OUTPUT--------
//Loop Existence : true

Cheers!
Bragaadeesh.

5 comments:

Unknown said...

Amazing Blog!!! wish I could have found it earlier.. Have a big interview tomorrow, would have been great help..

Ameya said...

Why did u not add this code as a part of singlyLinkedList.java ? what was a need to create another class

lakshmi narayana said...

When your while loop in doesLoopExist method terminate if it List doesn,t have any loop.

Aashish said...

You can find out the cycle or loop in a single linked list by using two pointer approach.
Below link can be useful to find out the algorithm to find cycle or loop in linked list

Find out loop or cycle in linked list in java

Amitesh said...

Check this out!
http://mybigdataconcepts.blogspot.in/2014/09/hadoop-setup-and-understanding.html