图解算法：确定单链表有环，如何找到环的入口和长度？

一、序

本文继续給大家带来一道和单链表相关的算法题。

之前聊到，如何对单链表是否存在环进行检测（
戳我了解

），今天再来聊聊这个问题的进阶题：

• 一个单链表，如果有环，求环的入口。
• 一个单链表，如果有环，求环的长度。

链表这种结构，可以通过「指针」，将一组零散的内存块串联起来。那单链表，如果有环是一个什么情况？

如上图所示， 单链表中如果存在环，一定有且只有一个入口点
，进去了就别想出来，接下来我们看看如何找到这个环的入口。

二、检测单链表环的入口

2.1 哈希法

哈希法的思路很简单，如果单链表上有环，那必然有一个链表上靠后的结点的 next 指针，指向了一个靠前的结点。
那么我们就可以通过一次循环加一个 Set 的辅助集合，来在每次循环的时候，判断结点是否在 Set 中，如果没有则将结点存入 Set 并继续循环，有则找到了链表的入口。

ListNode detectCycle(ListNode head) {
  Set 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 步，最终会在链表环的入口处相遇。

既然 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 步，最终两个指针会在入环点相遇。
直接上代码。

public ListNode detectCycle(ListNode head) {
  ListNode slow = head, fast = head;  while (true) {
if (fast == null || fast.next == null)
return null;
    slow = slow.next;
    fast = fast.next.next;
if (fast == slow)
break;
  }  fast = head;
while (slow != fast) {
    slow = slow.next;
    fast = fast.next;
  }
return fast;
}

到这里这个问题就说清楚了，不过我看不少人还有一些小疑问，这里也一并解答。

前面说到，为了简化问题，我们的前提条件是环很大， 那么在环很小的时候呢？

大与小本身就是一个相对的概念，在链表成环的场景下，我们说环很大的意思是在慢指针走到入环结点时，快指针还没有走完一圈。也就是说，要满足这个条件 2F < C
，F 为链表头结点到入环结点的长度，C 为环长度，这里面有两个变量。
这就清晰了，要么真的是个很大的环，要么 F 的长度很短，都可以说是「小环」，此时慢指针走到入环结点时，快指针已经在环内空转了 n 圈了。
环小的情况，其实和环大的情况是一样的，只是人为的觉得快指针多跑了很多圈，好像更复杂一些，这里说两个思考模型，来帮助我们思考。

1.
小环展开成大环
。可以将小环循环铺开，虚拟展开成一个大环去理解。

2.
从单链表上，去掉环内空转的长度
。我们其实不关心链表表头到入环结点的实际距离，我们只是为了求入环点，所以可以直接将快指针在环内空转的距离，从单链表上去掉。

这 2 个思考模型，都是为了帮助我们更好的理解和抽象问题，其实在「小环」的场景下，慢指针走到入环结点时，快指针已经在环内空转了很多圈了，所以其实这并不影响我们计算的结果。
找到入环结点，那么环的长度的算法，就是单链表求长度的算法，很简单，这里就不上代码了。

三、小结时刻

本文聊到了单链表如果有环，如何找到环的入口。举了两个解决方案，分别是哈希法和双指针法，双指针的方式，理解起来有一些绕，不过按照本文的步骤，多思考一下应该就可以理解。
这道题也是 leetcode 上第 142 题，我也是看到不少人在评论里，对官方的公式有疑问，所以才有了这篇文章。
算法没什么取巧的，多写多练多思考才是正途。

今天就到这里，本文对你有帮助吗？ 留言、转发、点好看
是最大的支持，谢谢！

references：

https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode/

公众号后台回复成长『 成长
』，将会得到我准备的学习资料。