142. 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?

思路1：naive的使用Hashset，需要extra space

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

        return null;
    }
}

思路 2：双指针。最妙的在于俩人遇到后在让继续跑。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head==null){
            return null;
        }

        ListNode walk = head;
        ListNode run = head;
        while(run.next!=null&&run.next.next!=null){
            walk = walk.next;
            run = run.next.next;
            //check if there is a loop
            if (walk==run){
                //put any one to the start point, and let them run. They will meet at start point in loop
                run = head;
                while(walk!=run){
                    walk = walk.next;
                    run = run.next;
                }
                return walk;
            }
        }
        return null;
    }
}