题⽬描述

给⼀个链表，若其中包含环，请找出该链表的环的⼊⼝结点，否则，输出null 。

例如，输⼊{1,2},{3,4,5} 时，对应的环形链表如下图所示： 可以看到环的⼊⼝结点的结点值为3，所以返回结点值为3的结点。

给定的链表节点的结构：

思路及解答

借用HashSet

直接使⽤ HashSet ,历链表的时候，如果 HashSet 中不包含，则添加到 HashSet 中，如果链表中包含，说明已经回到环的第⼀个节点。Java 代码实现如下：

  • 时间复杂度：O(n) - 每个节点最多访问一次

  • 空间复杂度：O(n) - 最坏情况下需要存储所有节点

双指针

上⾯的做法时间复杂度为O(n)，由于借助了⼀个hashSet，空间复杂度也为O(n) 。那假设我们不需要使⽤额外的空间呢？怎么做呢？

使⽤快慢双指针，⼀个⼀次⾛⼀步，⼀个⼀次⾛两步，当两个重合在⼀起的时候，这时候，并不是环的⼊⼝节点。只能说明两个指针，⼀个⽐另外⼀个多⾛了若⼲圈，可能是⼀圈，可能是2， 3 圈。 ⽐如上⾯的，如果开始节点是A，环的⼊⼝是B，相遇的节点是C，那么

  • 慢指针⾛的距离是： S=AB+BC

  • 快指针⾛的距离是： 假设多⾛了n圈，2S = AB+(BC+CB)*n+BC，

即 2(AB+BC) = AB+(BC+CB)*n+BC，也就是AB+BC = (BC+CB)*n

假设n =1，那么AB = CB ,也就是当前位置到环的⼊⼝的⻓度，等于链表头到环的⼊⼝的位置。

因此相遇之后，我们将⼀个快指针移动到链表头，两个指针每次⼀步，直到相遇，这个时候，相遇的节点就是环的⼊⼝节点。

  • 时间复杂度： O(n)

  • 空间复杂度： O(1)

有的小伙伴可能就会问了，这里假设了n = 1，那n =2,3 … 呢？结论是：无论 n 是 2、3 还是任意正整数，最终结论 AB=CB 依然严格成立。

前面我们得到了 AB+BC = (BC+CB) * n，我们假设环的长度 BC+CB 为 X。那么就是 AB+BC=X * n

移项：AB=X * n−BC

我们把右边的 n 拆成 (n−1)+1，也就是把 n 圈拆成 “n−1 圈” 加上 “最后 1 圈”：AB=X * (n−1)+ X −BC

代入环的构成：因为环的一圈 X​ 是由 BC 和 CB 组成的，即 X = BC+CB。 所以， X − BC正好就等于 CB 。把这个代入上一步的式子，最终得到：AB = X * (n−1) + CB = (BC+CB) * (n−1) + CB

这个公式完美解释了为什么 n=2 或 n=3 时结论依然成立：

  • AB ：是从链表头走到环入口的距离。

  • CB ：是从相遇点 C 沿着环走回到入口 B 的距离。

  • (BC+CB) * (n−1) ：代表 (n−1)个完整的环。

当我们执行“找入口”的操作时： 我们将一个指针放回起点 A，另一个指针留在相遇点 C，两个指针每次都只走一步。

  • 当起点出发的指针走了 AB 的距离到达入口 B 时；

  • 相遇点出发的指针也走了 AB 的距离。根据上面的公式，它走的这段距离等于 “在环里转了 n−1 圈，最后又多走了 CB 的距离”。

  • 因为它本来就在 C 点，在环里转整数圈后还是会回到 C 点，然后再走 CB 的距离，恰好就停在了入口 B 。

所以，无论 n 是 1、2 还是 100，多出来的那些圈数只是让指针在环里“空转”了几圈，最终两个指针一定会在入口节点 B 处相遇。

标记法（破坏性解法）

通过修改节点结构来标记已访问的节点，适合可以修改链表的情况

  • 时间复杂度：O(n) - 线性遍历

  • 空间复杂度：O(1) - 但破坏了链表结构