54.环形链表2（寻找环形链表的入口节点--双指针法）

解法一：双指针法公式思想推倒

public class Solution {
    public ListNode detectCycle(ListNode head) {

        ListNode fast = head, slow = head;//此处两指针都从head开始（区别于环形链路1的题）


        //step1:进行第一次快慢指针相遇
        while (true) {

            //情况：这不是环路（同时保证没有空指针异常）
            if (fast == null || fast.next == null) {
                return null;
            }

            fast = fast.next.next;
            slow = slow.next;

            //两指针第一次相遇，说明是环路
            if (fast == slow){
                 break;
            }
        }

        //step2:进行第二次同速指针相遇在环的入口节点
        //fast重新指向head（节省空间）,开始一步一步走，构造第二次相遇
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

解法二：使用hashset

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

        return null;
        
    }
}