142.环形链表Ⅱ

难度：中等

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

**进阶：**你是否可以使用 O(1) 空间解决此题？

解题思路

联想 160. 相交链表 的哈希做法，显然这个题可以采用的暴力做法是：哈希集合 HashSet

我的思路：

设定一个哈希集合 hashSet 用来存储链表 head 里面的节点
遍历链表 head，对于遍历到的每个节点，判断该节点是否在哈希集合中，并将链表 head 中的每个节点加入哈希集合中
- 如果当前节点不在哈希集合中，则继续遍历链表 head
- 如果当前节点在哈希集合中，则说明目标节点已经找到，链表存在环，返回该节点
若链表 head 遍历结束仍没有找到目标节点，说明链表无环，返回 null

我的代码（哈希集合）

java

public ListNode detectCycle(ListNode head) {
    HashSet<ListNode> set = new HashSet<>();
    ListNode cur;
    //用head初始化hashSet
    for (cur = head; !set.contains(cur) && cur != null; cur = cur.next) {
        set.add(cur);
    }
    //链表无环
    return cur;
}

时间复杂度：O(n)

空间复杂度：O(n)

HashSet

结构特点：

HashSet 是一个没有重复元素的集合。它的底层结构是依靠 HashMap 来实现的。实现方式大致为：通过一个 HashMap 存储元素，元素是存放在 HashMap 的 Key 中，而 Value 统一使用一个 Object 对象。
HashSet 不保证元素的顺序，而且 HashSet 允许使用 null 元素。
HashSet 是 非同步的，如果多个线程同时访问一个 HashSet ，而其中至少一个线程修改了该 HashSet ，那么它必须保持外部同步。
HashSet 按 Hash 算法来存储集合的元素，因此具有很好的存取和查找性能。

使用和理解中需要注意的细节：

HashSet 中是允许存入null值的，但是在 HashSet 中仅仅能够存入一个null值。
HashSet 中存储元素的位置是固定的 HashSet 中存储的元素的是无序的，由于 HashSet 底层是基于 Hash 算法实现的，使用了 hashcode，所以 HashSet 中相应的元素的位置是固定的
必须小心操作可变对象（Mutable Object）如果一个 HashSet 中的可变元素改变了自身状态使得 Object.equals(Object)=true，那么将导致一些问题。

双指针法

思路解析

这道题可以使用 快慢指针法，分别定义 fast 和 slow 指针，同时从链表头结点出发，fast 指针每次移动两个节点，slow 指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，则说明这个链表有环。

问题是，在 fast 一步走两个节点，slow 一步走一个节点的情况下，如果链表有环，这两个指针一定会在环内相遇吗？会不会巧合般的永远错开呢？

答案是：fast 指针会先进入环中，并且 fast 指针和 slow 指针一定会在环中相遇。

证明过程：

显然 fast 指针先进入环中，我们假设环中一共有 e 个节点
当 slow 指针首次进入环中，来到环中第 1 个节点时，假设 fast 指针处在环中第 w + 1 个节点的位置，那么二者此时的正向距离为 w，显然 0 <= w < e
由于 slow 指针一步走一个节点，fast 指针一步走两个节点，那么二者的正向距离从 w 开始，每走 t 步，其正向距离为：(w + 2 * t - t) % e = (w + t) % e
显然，当 t 从 0 逐步增加到 e - w 的时候，两个指针的距离刚好为 0，此时二者相遇，并且根据上式可知 0 <= t < e - w < e，也就是说，此次相遇的时候， slow 指针在环中还未走完一圈

综上，我们证明了可以通过快慢指针法在链表中找到环。

那么第二个问题是，在找到环之后，如何找到环的入口？

假设从链表头结点到环入口的节点数为 x，环入口到 fast 指针与 slow 指针首次相遇节点的距离为 y，从相遇节点再到环入口的距离为 z。如图所示：

显然， fast 指针与 slow 指针首次相遇时： slow 走了 x + y 步，fast 走了 x + y + n (y + z) 步。

其中 n 的含义是： fast 指针在环内比 slow 多走了 n 圈才遇到 slow 指针，y + z 为环的长度。

因为 fast 指针一步走两个节点，slow 指针一步走一个节点，所以 fast 指针的位移 = 2 * slow 指针的位移，即：(x + y) * 2 = x + y + n (y + z)，化简得 x + y = n (y + z)

如果我们能求得 x，再令一个指针从链表头指针移动 x 步，就可以找到想找环形的入口。

所以将 x 单独放在等式左边：x = n (y + z) - y，再从 n ( y + z ) 中提出一个 ( y + z ) 来，整理公式之后为如下公式：x = (n - 1) (y + z) + z

注意：上式的 n 一定是大于等于 1 的，因为 fast 指针至少要多走一圈才能相遇 slow 指针。

由于 [(n - 1) (y + z) + z] % (y + z) = z，则 x % (y + z) = z，这就意味着，倘若从头结点出发一个指针 temp，从相遇节点也出发一个指针 slow，这两个指针每步只走一个节点，那么当 temp 走了 x 步的时候，temp 到达了环入口，slow 也刚好到达了环入口，此时二者刚好是第一次相遇。

代码展示

java

public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    
	// 使用快慢指针检测环
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，表示链表有环
        if (fast == slow) {
            // 从头节点和相遇点同时开始遍历，再次相遇点即为环的起始点
            ListNode temp = head;
            while (temp != slow) {
                temp = temp.next;
                slow = slow.next;
            }
            return temp;
        }
    }
    //链表无环
    return null;
}

时间复杂度：O(n)，快慢指针相遇前，指针走的次数小于链表长度，快慢指针相遇后，两个指针走的次数也小于链表长度，总体为走的次数小于 2 * n

空间复杂度：O(1)

总结

这道题目，不仅考察对链表的操作，而且还需要一些数学运算。

主要考察两知识点：

判断链表是否环
如果有环，如何找到这个环的入口

142.环形链表Ⅱ ​

解题思路 ​

我的代码（哈希集合） ​

HashSet ​

双指针法 ​

思路解析 ​

代码展示 ​

总结 ​