快慢指针，公司推导
定义：
fast 一次移动俩步
slow 一次移动一步
从head到环入口为x;
环内slow移动距离为y;
环内除去y剩余距离为z;
此时如果快慢指针相遇时快指针移动距离是慢指针的俩倍
2*（x+y） = x+y+n(y+z)
化简,提取一个y+z
x = （n-1）(y+z) +z;
分别考虑 n =1 和 n>1; 都一样
此时意味着x=z,即从head到入口 和 从快慢指针相遇的地点 ，这俩个每次只移动一个距离，直到相遇时即为入口
1public class DetectCycle {
2
3 private static class ListNode {
4 int val;
5 ListNode next;
6
7 ListNode() {
8 }
9
10 ListNode(int val) {
11 this.val = val;
12 }
13
14 ListNode(int val, ListNode next) {
15 this.val = val;
16 this.next = next;
17 }
18
19
20 }
21
22 /**
23 * 142. 环形链表 II
24 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
25
26 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
27
28 说明：不允许修改给定的链表。
29
30 进阶：
31
32 你是否可以使用 O(1) 空间解决此题？
33
34
35 示例 1：
36
37
38
39 输入：head = [3,2,0,-4], pos = 1
40 输出：返回索引为 1 的链表节点
41 解释：链表中有一个环，其尾部连接到第二个节点。
42 示例 2：
43
44
45
46 输入：head = [1,2], pos = 0
47 输出：返回索引为 0 的链表节点
48 解释：链表中有一个环，其尾部连接到第一个节点。
49 示例 3：
50
51
52
53 输入：head = [1], pos = -1
54 输出：返回 null
55 解释：链表中没有环。
56
57
58 提示：
59
60 链表中节点的数目范围在范围 [0, 104] 内
61 -105 <= Node.val <= 105
62 pos 的值为 -1 或者链表中的一个有效索引
63 * @param head
64 * @return
65 */
66 public ListNode detectCycle(ListNode head) {
67 /**
68 *
69 * 快慢指针
70 * 如果有环则必然相遇，相遇的位置就是头结点，返回环的入口节点，这个需要总结公式
71 * 如果没有环，则是遍历了所有节点依旧没有相遇
72 */
73 ListNode fast = head;
74 ListNode slow = head;
75 while(fast!=null && fast.next!=null){
76 fast = fast.next.next;
77 slow = slow.next;
78 if(slow == fast){
79 ListNode index1 = fast;
80 ListNode index2 =head;
81 while(index1!=index2){
82 index1 = index1.next;
83 index2 = index2.next;
84 }
85 return index2;
86 }
87 }
88 return null;
89 }
90}
