环形链表入口
环形链表的快慢指针相遇问题：
力扣链接：https://leetcode.cn/problems/linked-list-cycle-ii/
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果是这个链表，我们需要返回2号节点。
这道题目的做法就是快慢指针法，慢指针每次只走一个节点，快指针的速度是慢指针的两倍，快指针走两个节点。
环的存在会导致快慢指针进到圈后，快指针追上慢指针（快慢指针在环中相遇）。
Floyd算法：慢指针每次走一步，快是慢的两倍，当快和慢在环里相遇的时候，从起点出发的头指针和从相遇点出发的慢指针一样的速度一起同步走，再次和慢相遇就是在环的入口处。
一句话总结就是慢指针进到环形圈里后，慢指针还没走完一圈就会被快指针追上，就会有一个相遇点。而恰好 从链表起始位置到环入口的距离 就等于 从相遇点继续走到环入口的距离 （或者前者等于 后者+ 圈数*n）。这时候只需要两个慢指针（只要每次都走一步就行），一个从起始位置，另一个从相遇点，同步一起走，一定会在环入口相遇！
以下说的距离都是按照 指针走的方向 （顺时针）走的距离
整个过程需要明白的几个关键点如下：
- 慢指针从起始位置走到环入口处，快指针已在环中某位置。
- 快指针追赶慢指针直到相遇。
- 起始位置指针与慢指针同步走，一定在环入口相遇。
这里我们详细展开，当慢指针刚走到入口的时候（我们假设慢指针从开始走到入口走了 L 步）：
已知快指针比慢指针多走了 L 步，所以快指针初始的位置（Fast0点）应该距离入口点（Slow0点）距离 L 步。
慢指针走 n步，快指针走2n步，快只比慢多走n步。
接下来，只盯着慢指针看，慢指针进到环中，会在第一圈就被快指针追上，这个点就是快慢的相遇点。 快指针在圈里追慢指针，一定不会让慢指针跑完一整圈。也就是说，慢指针在进入圈内的时候，会在完成一圈之前就被快指针抓住。所以在慢指针进圈之后，不需要假设他们追及n圈。
核心在于快追慢的过程：快指针的速度是慢指针的两倍，那么快指针想要追上慢指针，慢指针每回合走一步，快指针就走两步，快指针就会离慢进一步，所以此时快到慢指针之间的距离（慢刚到达环入口时候）就是快指针追上慢指针需要的回合数，这恰好也是慢指针进入环中走的距离。（慢指针每回合走一步，回合数也刚好等于慢指针走的步数）
如图可以看到，我们能够直到慢指针最终在环中走到相遇点的距离是环周长- L，那么从相遇点再走L就可以再次到达入口点，这段距离是 L ，恰好也是从链表起始点到环形入口点的距离。
所以此时我们从起始位置和相遇点一起同步走（每次一步），就一定可以刚好在环入口的位置相遇。那么我们就可以使用判断条件得到环入口的位置了。
其实上面这种情况只是其中的一种好理解的情况，没什么变化容易理解，当这个可以理解之后，另一种情况也就没什么难度了。 为了让问题更加清晰的展示，实际上可以分为两种情况：
- 一种是环形周长很大，而前半部分（从开始到入口处）很短，这样当慢指针走到环形圈入口时候，快指针在环形圈中也不会走满一圈。（我们刚刚的过程就是这个情况）
最终结果就是 从链表起始位置到环入口的距离 就等于 从相遇点继续走到环入口的距离
● 一种是环形周长很小，而前半部分很长，这样当慢指针走到环形入口时候，快指针已经走了好多圈了。（接下来描述的情况）
最终结果就是 从链表起始位置到环入口的距离 就等于 从相遇点继续走到环入口的距离 + n*圈长
当环周长小于前半部分的时候：快指针会多走几圈，然后慢指针才到达入口处。这个圈数无关紧要，我们只需要知道起始位置到环入口的距离 L = r + nd（走了很多圈后最后一圈从起点再走r步长）
同样地，还是将相遇点作为研究的位置进行计算。这里我就偷懒使用b站一个up的手绘图来进行描述。
当慢指针到达环入口时候，环入口到快指针初始位置的距离是 r ,那么快指针需要环周长 - r 的回合追上慢指针和它相遇。因此慢指针从相遇点走到环入口需要走 r 步。而此时如果有另一个指针从起始位置出发，和慢指针同步行走，他们一定会在环入口相遇。因为前面我们已经知道了L和r的关系： L = r + nd。
这表示，慢指针从相遇点走到了环入口的时候，一起同步走的头指针（从其实位置走的指针）也只走了r，头指针此时距离环入口还剩下 L-r = nd 的步数，而剩下的回合中，头指针走到环入口的时候，慢指针恰好会走完n圈后也到达环入口。
所以最终这两种情况都可以使用一套逻辑进行实现： 1.快慢一起出发，快一次走两步，慢一次走一步。 2.快慢相遇时候停下来，头指针和慢指针同步走直到相遇，结果就是环入口。
public ListNode detectCycle(ListNode 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 temp;
}
}
//不存在环
return null;
}