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.