Linked List Cycle II

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

Note:Do not modify the linked list.

Follow up

Can you solve it without using extra space?

Analysis

When fast and slow meet at point p, the length they have run are 'a+2b+c' and 'a+b'.

Since the fast is 2 times faster than the slow. So a+2b+c == 2(a+b), then we get 'a==c'.

So when another slow2 pointer run from head to 'q', at the same time, previous slow pointer will run from 'p' to 'q', so they meet at the pointer 'q' together.

Solution

    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                ListNode slow2 = head;
                while (slow2 != slow) {
                    slow = slow.next;
                    slow2 = slow2.next;
                }
                return slow;
            }
        }
        return null;
    }

My Solution

(use extra space)

public ListNode detectCycle(ListNode head) {
    HashSet<ListNode> set = new HashSet<>();
        while (head != null && set.add(head)) {
            head = head.next;
        }
        return head;
}