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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

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

龟兔赛跑（快慢指针）法：

/*** @author mac* @date 2020/11/11-19:54*/
public class t142_环形链表II {public ListNode detectCycle(ListNode head) {// 如果链表是null，或者只有一个就没有环，直接返回nullif (head == null || head.next == null) {return null;}// 设置慢节点ListNode i = head;// 设置快节点ListNode j = head;// 循环遍历找重合点while (true) {// 如果快指针遍历结束，证明没有环if (j.next == null || j.next.next == null) {return null;}// 慢指针一次移动一位i = i.next;// 快指针一次移动两位j = j.next.next;// 如果快慢指针重合，证明有环if (i == j) {break;}}// 将慢指针重新指向头结点i = head;// j指针 位置不变 ，将i指针重新 指向链表头部节点 ；i和j同时每轮向前走n步； 此时f=0,s=nb；// 当i指针走到f=a步时，j指针走到步s=a+nb，此时 两指针重合，并同时指向链表环入口 。// 重新循环，返回索引为 1 (pos = 1)的链表节点(链表环入口)while (i != j) {i = i.next;j = j.next;}return i;}/*** Definition for singly-linked list.*/class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}
}

二、哈希表法

    public ListNode detectCycle(ListNode head) {// 如果链表是null，或者只有一个就没有环，直接返回nullif (head == null || head.next == null) {return null;}// 创建一个空的Hash表Set set = new HashSet<ListNode>();ListNode i = head;// 从头节点开始遍历while (i != null) {// set中如果存在就直接返回if (set.contains(i)) {return i;} else {// 如果不存在，则add到hash表中set.add(i);}i = i.next;}// 循环结束return null;}