Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Example:

Given -21->10->4->5, tail connects to node index 1，return 10

Solution:

We could use two pointers to detect cycle. We run a slow pointer which moves one step at a time and a fast pointer which is two times faster than slow pointer. If the fast pointer reaches null, this mean there is no cycle, otherwise, fast pointer will be trapped in the cycle until the slow pointer meet it up in the cycle.

When we find the cycle (slow pointer == fast pointer), we could start another pointer run the same speed as slow pointer. Once they met, the node they met on is the start of the cycle.

Proof:

When slow and fast meets, slow has travelled t + k _nodes where _t is the number of nodes out side the cycle and fast has travelled 2t + 2k nodes. In this 2t + 2k, 1t is used to travel into the cycle and 1k is used to catch up slow pointer (since slow pointer also moved k nodes in the cycle). Therefore, the size of the cycle is t + k.

Since slow has travelled k nodes in the cycle, slow will come back to the start node of the cycle after another t step.

Code:

/**
 * 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) {  
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != slow) {
            if (fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        while (head != slow.next) {
            slow = slow.next;
            head = head.next;
        }
        return head;
    }
}