Showing posts with label loop. Show all posts
Showing posts with label loop. Show all posts

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.