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

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

不允许修改 链表。

方法一：哈希表

思路：set中的元素特点：无序、不可重复

• 时间复杂度：O(N)

• 空间复杂度：O(N)

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

方法二：快慢指针

将一个带环的链表长度分为三部分：环外长度(a)，入环到快慢指针相遇的地方长度(b)，环的剩余部分长度(c)，设相遇时fast已经跑了n圈环，则fast跑的路程为a+n(b+c)+b

fast走的长度为slow的两倍：

2(a+b) = a+n(b+c)+b

则：a+b=n(b+c)

则：a=(n-1)b+nc=n(b+c)-b

所以此时再定义一个pos指向head，让slow跟随着pos一同移动，在pos移动到a时，会和slow相遇（slow == pos）

public ListNode detectCycle(ListNode head){
    ListNode slow = head, fast = head;
    while(fast != null){
        slow = slow.next;
        if(fast.next != null) fast = fast.next.next;
        else return null;
        if(slow == fast){ // 有环
            ListNode pos = head;
            while(pos != slow){
                slow == slow.next;
                pos == pos.next;
            }
            return pos;
        }            
    }
    return null;
}