Saturday, January 16, 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.

3 comments:

Minal Bagade 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.