[Leetcode] Linked List Cycle II

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

Follow up:
Can you solve it without using extra space?

要求找到链表中，环开始的地方，如果没有环则直接返回null。使用Hashset可以很方便的找到环开始的地方，即第一次在Hashset中找到的节点。

public ListNode detectCycle(ListNode head) {
        HashSet set = new HashSet();
        ListNode temp = head;
        
        while(temp != null) {
            if(set.contains(temp) == true) {
                return temp;
            }
            else {
                set.add(temp);
                temp = temp.next;
            }
        }
        
        return null;
    }

上面的方法空间复杂度为O(n)，可以再次使用快慢指针使得空间复杂度降为O(1)。可以证明，快慢指针相遇的地方到环开始的距离等于链表头到环开始的距离，利用改性质可以找到环开始的地方。

public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        
        do {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) break;
        }while(slow != null && fast != null && fast.next != null);
        if(fast == null || fast.next == null) {
            return null;
        }
        ListNode temp = head;
        while(temp != slow) {
            slow = slow.next;
            temp = temp.next;
        }
        
        return temp;
    }