[LintCode] #102 LinkedList Cycle II

N - distance from head to the node of cycle begins
M - the number of nodes in the cycle
K - the distance from node of cycle begins to the node fast and slow pointer meet

fast = N + xM + K
slow = N + yM + K
fast = 2 slow

=> N + K = (x - 2y) * M

We know when fast and slow meet, they are at Kth node in the cycle, it takes N steps to move from the Kth node in the cycle to the first node in the cycle. How to move this N steps? We know the distance from head to the node where cycle begins is also N. So, we just need to move fast or slow to head and keep step+1 until the two pointers meet.

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: The node where the cycle begins. 
     *           if there is no cycle, return null
     */
    public ListNode detectCycle(ListNode head) {  
        // write your code here
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                fast = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}