142、环形链表||

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

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

进阶挑战：不允许修改给定的链表。

方法：快慢指针（双指针）

public class Huanxinglianbiao2 {
    public ListNode detectCycle(ListNode head){
        //设置快慢指针
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            //快指针走两步
            //慢指针走一步
            fast = fast.next.next;
            slow = slow.next;

            //如果fast == slow确认有环
            //找到快慢指针的相遇点，再相遇点快指针回到head，慢指针保持不动
            //他们再以相同的速度前进，当他们再次相遇的点，就是环形入口的入口点了
            if (fast == slow){
                fast = head;
                while (fast!=slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                //返回环的入口
                return fast;
            }
        }
        //遍历链表结束，没有找到环，则返回空；
        return null;
    }
}