142 Linked List Cycle II

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

Note:Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

        A   ----      B

                 /          \

                |            D

                  \ _ ______/

找圆环开始的位置，B

Because the speed of fast is twice of the slow, so the distance is also two times of slow.

When slow and fast meet, the distance of fast is twice of the slow, if they meet at D

2 (AB + BD) = AB + BD + DB + BD ;

So AB = DB

So if you set another node start from head, and go together with slow, they will meet at where the cycle begins

Problem is

this time you set fast = head. not head.next

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode temp = head;
                while (temp != slow) {
                    temp = temp.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}

142 detect cycle start pos

class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
         int slow = nums[0];
        int fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        fast = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}