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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Follow-up:

Can you solve it without using extra space?

单链表中的环二。题意是给一个链表，如果这个链表中有环，请return环的起点；若没有，return null。

时间O(n)

空间O(1)

思路；

快慢指针：如相遇则有环，第一次相遇后，快指针回到头节点，开始分别都以一步的方式往前走，第二次相遇则是入环节点

因为快慢指针的速度是一个2步一个1步，所以当两个指针相遇的时候，fast走过的长度一定是slow的两倍。两者相遇的地方一定是环的起点。

 

public class Solution {
    public ListNode detectCycle(ListNode head) {
       if(head==null || head.next==null || head.next.next==null){
           return null;
       }
        ListNode s=head.next;
        ListNode f=head.next.next;
        while(s!=f){
            if(f.next==null||f.next.next==null){
                return null;
            }
             f=f.next.next;
            s=s.next;
           
        }
        //f回到头节点，s停，f,s一步一步往前走，相遇了则是入环节点
        f=head;
        while(s!=f){
             s=s.next;
            f=f.next;
           
        }
        return s;

    }
}