142. Linked List Cycle II

1. using map, but this will use extra space:(26ms)

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_map<ListNode*, int> m;
        ListNode* p=head;
        int cnt=0;
        while(p!=NULL){
            if(++m[p] == 2)return p;
            p=p->next;
        }
        return NULL;
    }
};



2. find out there is a circle first;
    then swipe each node to check whether there are in circle, the first in circle is the head of the circle.



3. using the 'find intersection in a merging lists' in http://xiamenhai.blogspot.com/2015/10/leetcode-intersection-of-two-linked.html.