public static int DetectRemove(LinkedList head){
LinkedList slow = head,fast=head;
if(head==null)
return 0;
while(slow != null && fast !=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow.value == fast.value){
removeLoop(slow,head);
return 1;
}
}
return 0;
}
public static void removeLoop(LinkedList loopNode , LinkedList head) {
// First find out the length of the loop
int loopLength =1;
LinkedList loopNodeCopy = loopNode;
while(loopNodeCopy.next.value!= loopNode.value){
loopNodeCopy = loopNodeCopy.next;
loopLength++;
}
System.out.println("Loop Length :" + loopLength);
LinkedList ptrToHead = head;
LinkedList ptrToKth = head;
//Move one pointer to Kth node
int k = 0;
while(k<loopLength) {
ptrToKth = ptrToKth.next;
k++;
}
System.out.println("Kth node:" + ptrToKth.value);
// Increment both pointers(from head and one frm Kth node)
// prev to keep track of the last node in d loop
LinkedList prev = null;
while (ptrToHead.value != ptrToKth.value){
prev=ptrToKth;
ptrToHead = ptrToHead.next;
ptrToKth = ptrToKth.next;
}
prev.next=null;
LinkedList.Display(head);
}
Sunday, December 4, 2011
Detect and remove Loop in LL
Labels:
LinkedList
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment