一、序
本文继续給大家带来一道和单链表相关的算法题。
之前聊到，如何对单链表是否存在环进行检测，今天再来聊聊这个问题的进阶的题：
- 一个单链表，如果有环，求环的入口。
- 一个单链表，如果有环，求环的长度。
链表这种结构，可以通过「指针」，将一组零散的内存块串联起来。那单链表，如果有环是一个什么情况？
如上图所示，单链表中如果存在环，一定有且只有一个入口点，进去了就别想出来，接下来我们看看如何找到这个环的入口。
二、检测单链表环的入口
2.1 哈希法
哈希法的思路很简单，如果单链表上有环，那必然有一个链表上靠后的结点的 next 指针，指向了一个靠前的结点。
那么我们就可以通过一次循环加一个 Set 的辅助集合，来在每次循环的时候，判断结点是否在 Set 中，如果没有则将结点存入 Set 并继续循环，有则找到了链表的入口。
<code>ListNodedetectCycle(ListNodehead){
Set<listnode>visited=newHashSet<>();
ListNodenode=head;
while(node!=null){
if(visited.contains(node))
returnnode;
visited.add(node);
node=node.next;
}
}
/<listnode>/<code>这种方式相对暴力，但是很好理解，只是需要额外消耗一个 Set 结构的空间，所以空间复杂度是 O(n)。同时它也是一种检测单链表是否有环的解法。
2.2 双指针法（Floyd算法）
在检测单向链表是否有环的解法中，还有一个比较经典的双指针来辅助计算，就是快慢指针。
解题思路就是使用 2 个指针，快指针每次走 2 步，慢指针每次走 1 步，如果链表有环，那么它们肯定可以在环中相遇。就像两个人在圆形的赛道上赛跑，一个跑的快另一个跑的慢，最终肯定是跑的快的人，追上了跑的慢的。
不过想用双指针来确定单链表环的入口，思路上还有一些绕。
简单来说，当快、慢两个指针首次相遇后，再用两个指针，指针 A 指向首次相遇的结点，指针 B 移动到单链表的头结点，然后两个指针分别每次向前移动 1 步，最终相遇的地方，就是单链表成环的入口。
先来说说思路，我们首先假设环足够大，那么在这道题里，存在 3 个关键结点：链表头结点、环入口结点、快慢指针首次相遇结点。通过这三个点可以将指针移动的路径，分为 3 个区域。
从前面介绍的思路来说，当找到首次相遇点后，使用两个指针，指针 A 指向首次相遇的点，指针 B 指向链表头，两个指针继续同时向前走，每次走 1 步，最终会在链表环的入口处相遇。
既然 A、B 两个指针，每次走 1 步，最终相遇的点，就是环的入口，那么从步长来说 F = b，但是为什么它们是相等的呢？Leetcode 給出一个 F = b 的指导公式，很清晰，我贴出来大家参考一下。
如果公式不好理解，我再用文字描述一下思路。为了简化问题，我们只考虑环很大的情况（后面解释），最少是 2 倍于表头结点到环入口结点的距离。
1. 首先每次快指针走 2 步，慢指针走 1 步，假设慢指针走了 F 步走到了环的入口处，此时快指针走了 2F 步。
2. 当慢指针在环的入口点时，此时快指针距离入口点，已经走了 F 步了，多说一句 F 就是链表头到环入口结点的距离。此时慢指针（slow） 和快指针（fast）都在环上，可将环分为 n（红色）和 b（蓝色） 两个区域，此时 b == F。
3. 接下来快、慢指针继续向前走，快指针想要追上慢指针，只有一种情况，就是慢指针走了 b 步，而快指针走了 2b 步，跨越了环入口结点。可以简单理解这个圆环，以环入口点到圆心为轴，翻转了一次。
到这里应该就清晰了，剩余的 b 区域，其实就等于 F 区域，所以再用两个指针，分别在相遇结点和头结点继续向前走，每次走 1 步，最终两个指针会在入环点相遇。
直接上代码。
<code>publicListNodedetectCycle(ListNodehead){
ListNodeslow=head,fast=head;
while(true){
if(fast==null||fast.next==null)
returnnull;
slow=slow.next;
fast=fast.next.next;
if(fast==slow)
break;
}
fast=head;
while(slow!=fast){
slow=slow.next;
fast=fast.next;
}
returnfast;
}/<code>到这里这个问题就说清楚了，不过我看不少人还有一些小疑问，这里也一并解答。
前面说到，为了简化问题，我们的前提条件是环很大，那么在环很小的时候呢？
大与小本身就是一个相对的概念，在链表成环的场景下，说环很大的意思是在慢指针走到入环结点时，快指针还没有走完一圈。也就是说，要满足这个条件 2F < C，F 为链表头结点到入环结点的长度，C 为环长度，这里面有两个变量。
这就清晰了，要么真的是个很大的环，要么 F 的长度很短，都可以说是「小环」，此时慢指针走到入环结点时，快指针已经在环内空转了 n 圈了。
环小的情况，其实和环大的情况是一样的，只是人为的觉得快指针多跑了很多圈，好像更复杂一些，这里说两个思考模型，来帮助我们思考。
1. 小环展开成大环。可以将小环循环铺开，虚拟展开成一个大环去理解。
2. 从单链表上，去掉环内空转的长度。我们其实不关心链表表头到入环结点的实际距离，我们只是为了求入环点，所以可以直接将快指针在环内空转的距离，从单链表上去掉。
这 2 个思考模型，都是为了帮助我们更好的理解和抽象问题，其实在「小环」的场景下，慢指针走到入环结点时，快指针已经在环内空转了很多圈了，所以其实这并不影响我们计算的结果。
找到入环结点，那么环的长度的算法，就是单链表求长度的算法，很简单，这里就不上代码了。
三、小结时刻
本文聊到了单链表如果有环，如何找到环的入口。举了两个解决方案，分别是哈希法和双指针法，双指针的方式，理解起来有一些绕，不过按照本文的步骤，多思考一下应该就可以理解。
这道题也是 leetcode 上第 142 题，我也是看到不少人在评论里，对官方的公式有疑问，所以才有了这篇文章。
算法没什么取巧的，多写多练多思考才是正途。
今天就到这里，本文对你有帮助吗？留言、转发、点收藏是最大的支持，谢谢！
在头条号私信我。我会送你一些我整理的学习资料，包含：Android反编译、算法、设计模式、虚拟机、Linux、Kotlin、Python、爬虫、Web项目源码。
閱讀更多 承香墨影 的文章
