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;
}
}