题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
示例 2：
示例 3：
提示：
- 链表中节点的数目范围在范围 [0, 104] 内
- -105 <= Node.val <= 105
- pos 的值为 -1 或者链表中的一个有效索引
题目解析
基于 141. 环形链表 的解法，直观地来说就是当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
我们假设快慢指针相遇时，慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步：
- fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。
- 假设相遇点距环的起点的距离为 m，那么环的起点距头结点 head 的距离为 k – m，也就是说如果从 head 前进 k – m 步就能到达环起点。
- 巧的是，如果从相遇点继续前进 k – m 步，也恰好到达环起点：
所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k – m 步后一定会相遇，相遇之处就是环的起点了。
参考代码
以下为 Java 代码。
复杂度分析
- 时间复杂度：O(N)，其中 N 为链表中节点的数目。
- 在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度；
- 随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 O(N)+O(N)=O(N)。
- 空间复杂度：O(1)。
