Given a linked list, return the node where the cycle begins.

If there is no cycle, returnnull.

Have you met this question in a real interview?

Yes

Example

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

1. no extra space

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
        if (head == null) {
            return null;
        }


        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null) {

            fast = fast.next.next;
            slow = slow.next;

            if (fast != slow) {
                continue;
            }


            while (head != slow) {
                head = head.next;
                slow = slow.next;
            }
            return head;
        }

        return null;
    }

}