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:
Amazing Blog!!! wish I could have found it earlier.. Have a big interview tomorrow, would have been great help..
Why did u not add this code as a part of singlyLinkedList.java ? what was a need to create another class
When your while loop in doesLoopExist method terminate if it List doesn,t have any loop.
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
Check this out!
http://mybigdataconcepts.blogspot.in/2014/09/hadoop-setup-and-understanding.html
Post a Comment