一、序
本文继续給大家带来一道和单链表相关的算法题。
之前聊到，如何对单链表是否存在环进行检测，今天再来聊聊这个问题的进阶的题：
- 一个单链表，如果有环，求环的入口。
- 一个单链表，如果有环，求环的长度。
链表这种结构，可以通过「指针」，将一组零散的内存块串联起来。那单链表，如果有环是一个什么情况？
如上图所示，单链表中如果存在环，一定有且只有一个入口点，进去了就别想出来，接下来我们看看如何找到这个环的入口。
二、检测单链表环的入口
2.1 哈希法
哈希法的思路很简单，如果单链表上有环，那必然有一个链表上靠后的结点的 next 指针，指向了一个靠前的结点。
那么我们就可以通过一次循环加一个 Set 的辅助集合，来在每次循环的时候，判断结点是否在 Set 中，如果没有则将结点存入 Set 并继续循环，有则找到了链表的入口。
Listnode detectCycle(ListNode head) {
Set<ListNode> visited = new HashSet<>();
ListNode node = head;
while(node != null) {
if (visited.contains(node))
return node;
visited.add(node);
node = node.next;
}
}
这种方式相对暴力，但是很好理解，只是需要额外消耗一个 Set 结构的空间，所以空间复杂度是 O(n)。同时它也是一种检测单链表是否有环的解法。
2.2 双指针法（Floyd算法）
在检测单向链表是否有环的解法中，还有一个比较经典的双指针来辅助计算，就是快慢指针。
解题思路就是使用 2 个指针，快指针每次走 2 步，慢指针每次走 1 步，如果链表有环，那么它们肯定可以在环中相遇。就像两个人在圆形的赛道上赛跑，一个跑的快另一个跑的慢，最终肯定是跑的快的人，追上了跑的慢的。
不过想用双指针来确定单链表环的入口，思路上还有一些绕。
简单来说，当快、慢两个指针首次相遇后，再用两个指针，指针 A 指向首次相遇的结点，指针 B 移动到单链表的头结点，然后两个指针分别每次向前移动 1 步，最终相遇的地方，就是单链表成环的入口。
先来说说思路，我们首先假设环足够大，那么在这道题里，存在 3 个关键结点：链表头结点、环入口结点、快慢指针首次相遇结点。通过这三个点可以将指针移动的路径，分为 3 个区域。
从前面介绍的思路来说，当找到首次相遇点后，使用两个指针，指针 A 指向首次相遇的点，指针 B 指向链表头，两个指针继续同时向前走，每次走 1 步，最终会在链表环的入口处相遇。
