给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。

HashSet求解

时间复杂度：O(n)

空间复杂度：O(n)


/**
 * 求链表中环的入口节点
 * 用Set 保存已经访问过的节点，遍历整个列表并返回第一个出现重复的节点。
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 *
 * @param head 链表头节点
 * @return 是否循环链表
 */
public static ListNode detectCycle(ListNode head) {
    Set<ListNode> nodes = new HashSet<>();
    while (head != null) {
        if (nodes.contains(head)) {
            return head;
        }
        nodes.add(head);
        head = head.next;
    }
    return null;
}

Floyd算法求解

Floyd判圈算法，也称龟兔赛跑算法，可用于判断链表、迭代函数、有限状态机是否有环。如果有，找出环的起点和大小。时间复杂度O(n)，空间复杂度O(1)。

求解原理

假设相遇于 D 点，则快指针应该这时刚好套慢指针一圈（ 2 倍速的必然结果，可以数学证明），
则此时快指针走的路程为 AB + BCDEB + BD （用 BCDEB 表示一圈）(字母序表示方向，AB 表示 A -> B)

慢指针走的路程为 AB + BD；
由于 SS(快指针) = 2 * S(慢指针) （因为 2 倍速）（ SS 表示总路程），
AB + BCDEB + BD = 2 * (AB + BD) ——-(1)
AB + BD = BCDEB ——-(2)
上式表明此时慢指针走过的全部路径刚好一圈，我们的目标是获得 BB 点这一入环点，又根据一圈的关系，有一圈剩余部分，
DB = BCDEB - BD ——-(3)
联立式(2)(3)，有
AB = DB ——-(4)
上式表示 DD 到 BB 的距离和 AA 到 BB 的距离是相等的

在慢指针从相遇点 DD 继续向前走 DBDB 个长度，一个新指针从 AA 起始点用同样速度。
开始走，两个指针将会在 BB 点相遇，而 BB 点也正是我们想要的相遇点。

代码


/**
 * Floyd求链表中环的入口节点
 * 1.定义快慢指针求相遇点，快指针比慢指针快2倍；
 * 2.在相遇点，定义1个指针从头，1个指针从相遇点，一起开始逐步前进，下次相遇点即为环入口；
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 *
 * @param head 链表头节点
 * @return 是否循环链表
 */
public static ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    //寻找相遇
    ListNode slow = head.next;
    ListNode fast = head.next.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    //寻找环入口
    ListNode meetSlow = head;
    while (meetSlow != fast) {
        fast = fast.next;
        meetSlow = meetSlow.next;
    }
    return meetSlow;
}