Monday, January 12, 2015

Cycle detection in linked list

There are set of cycle detection problems, such as detecting cycle in linked list, detecting cycle in graph (directed or undirected), detection starting point of repeating sequence. See wiki page for formal definition: http://en.wikipedia.org/wiki/Cycle_detection

Here I represents the cycle detection in linkedList using fast and slow pointers.



public class Node{
Object data;
Node next;
}
public Node findCyclePoint(Node head){
if(head==null)
return null;
Node slow = head, fast = head.next;
while(slow!=fast && fast!=null && fast.next!=null){
slow = slow.next; fast = fast.next.next;
}
fast = head;
while(slow!=fast && slow!=null){
slow = slow.next; fast = fast.next;
}
return fast;
}

No comments:

Post a Comment