题目：

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。

示例 2： 输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。 示例 3： 输入：head = [1], pos = -1 输出：no cycle 解释：链表中没有环。 进阶： 你是否可以不用额外空间解决此题？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处

---

用HashSet解决：

因为hashset只能存储不重复的对象，利用这一特性，直接遍历这个链表，当出现重复的对象时，我们直接就找到了环形链表的入口，如果遍历结束还是没有重复对象，那么就说明不是环形链表。 这个方法逻辑很简单，但是创建了hashset，用了额外的空间O（n）。

public class Solution { public ListNode detectCycle(ListNode head) { Set<ListNode> visited = new HashSet<ListNode>(); ListNode node = head; while (node != null) { if (visited.contains(node)) { return node; } visited.add(node); node = node.next; } return null; } }

---

快慢指针

快慢指针用通俗一点的说法就是平时我们在跑步时，两个人只要不停下来，那么跑的快的那一个总有可能超过跑过慢的，这时他们就会相交。 如果题目给出的是环形链表，那么我设置两个指针，一个每次走一步称为slow，一个每次走两步称为fast，fast总会追上slow。 如果给出的不是环形链表，则会遇到指针等于null的情况，此时判断没有环，返回null。

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast = head, slow = head; while (true) {//判断是否有环 if (fast == null || fast.next == null) return null; fast = fast.next.next; slow = slow.next; if (fast == slow) break; } ListNode temp = head; while (slow != temp) { slow = slow.next; temp = temp.next; } return temp; } }

设从head需要走 a 步到达环的入口，如果环存在的话，再走 b 步可以再次到达该入口（即环的长度为b）。 假设相遇时slow走过的长度为

s = a+x

当快慢指针相遇时，快指针已经至少走完一圈环了，不妨设相遇时走了完整的m圈(m >= 1)，则fast走过

f = a + mb + x

由于快指针fast 走的路长始终是慢指针的 2倍:

f = 2s ——> f = 2mb

可以在链表的开头初始化一个新的指针,称其为 temp, 此时 temp距离环的入口的距离为 a，当temp和fast同时走过a步后，f = 2mb+a，fast刚好和temp在环的入口处相遇。

---