Linked List Cycle II

问题描述（难度中等）

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer poswhich represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

方法一：用HashSet检查重复

这里将每个节点看作独立的对象，散列到HashSet中，如果出现了重复节点，就直接返回当前的节点，那么该节点就是环的起点。这种方法比较直观，当然需要消耗n的空间复杂度。穿插记录下这里的每个节点都会根据hashCode去散列到数组不同的位置，我们没有重写hashCode和equals方法，那么默认每个object都有不同的hashCode，并且eqauls方法也只返回引用的比较结果。Effective Java中对对象重写equal方法有个规范，需要同时重写hashCode方法，主要为了避免用当前类对象作为Hash这种数据结构的key的时候会导致不一致，equals相等但是hashCode不想等，导致逻辑上认为相等的一个对象被散列到两个链表上。

方法一代码

private HashSet<ListNode> hashSet=new HashSet<>();
    public ListNode detectCycle(ListNode head) {
        while (head!= null){
            if(hashSet.contains(head)){
                return head;
            }else {
                hashSet.add(head);
            }
            head = head.next;
        }
        return null;
    }

看起来逻辑是非常清晰的，实现非常的简单。

方法二：快慢指针遍历

方法一虽然实现比较简单但是需要n的空间复杂度，在判断链表是否有环的练习题我们同样可以用快慢指针，返回相遇点，但是这里需要寻找环的起点，这个自己没有想到好的solution，从disscuss中发现了一些宝藏男孩。这里我们简单推理重现一下。

这里假设我们慢指针以一步的步长往前走，快指针两步走，最终相遇在Meet Pointer的位置，慢指针走了S的距离，快指针走了2S距离，根据图中可以推导出A=C+(N-1)*loop，也就是说设置两个起点一个从链表头部开始，一个从Meet Pointer开始，分别往下遍历，最终会在Circle Start Pointer相遇。整个算法的过程是第一次循环找到Meet Pointer,第二次循环找到Circle Start Pointer。

方法二代码

public ListNode detectCycleUsingPointer(ListNode head){
        if(head ==null || head.next == null || head.next.next ==null){
            return null;
        }
        ListNode pointer1=head.next;
        ListNode pointer2=head.next.next;
        //step1:找出环的位置
        while (pointer1!=pointer2){
            if(pointer2 ==null || pointer2.next ==null){
                return null;
            }
            pointer2 =pointer2.next.next;
            pointer1 = pointer1.next;
        }
        //step2:重新开始一遍扫描环
        while(head != pointer1){
            head=head.next;
            pointer1=pointer1.next;
        }
        return head;
    }

总结

第一种方式较为直观，实现上较为简单，但是需要占用n的空间复杂度。第二种时间空间效率更高，但是实现上一开始比较难想到。