Finding the cycle node in a list

We will need to break the problem into 2 parts, first find if a cycle is available in the list, second where does the cycle starts.

Finding the cycle can be done using tortoise and hare algorithm where we have two pointers in the start. first pointer will move at a speed of one node at a time and second pointer moves at a speed of 2. If these two pointers meet a point, we know there is a cycle.

Next step is to get count of elements in the cycle, which is easy after finding any node in cycle as we did using tortoise and hare algorithm. All we need to do is to take the node we found in the cycle, and move to next until we reach back to original node.

Last step, is to reposition two pointers at start. Next make one of the pointers get a lead of nodes equal to cycle size. Finally start moving the two pointers at a speed of 1, remember one pointer started from start node and second started at Nth node, where N is size of cycle. At the point where these meet is the node where the cycle starts.


public ListNode detectCycle(ListNode a) {
		ListNode pt1=a;
		while(pt1!=pt2 &&!=null &&!=null &&!=null) {;;
		if( || || return null;
		//we have a cycle, lets check number of nodes
		ListNode l = pt1;
		int count =0;;
		while(pt1!=l) {
		for(int i=0;i