链表中环的入口节点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

方法1：用集合的方法
遍历链表，如果集合中没有这个节点，就放进集合，如果集合中有这个节点，就返回这个节点（该节点就是链表环的入口节点）
如果p为NULL了，证明该链表没有环，返回NULL

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        unordered_set<ListNode*> s;
        ListNode* p=pHead;
        while(1)
        {
            if(s.find(p)==s.end())
            {
                s.insert(p);
                p=p->next;
            }
            else
                return p;
            if(p==NULL)
                return NULL;
        }
    }
};

方法2：快慢指针的方法
定义一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步；
如果快指针指向了NULL，则没有环；
若快慢指针相遇了，则证明一定有环；
此时，让快指针返回头结点，两个指针同时往前走，当两指针再次相遇时，该节点则为环的入口节点

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(pHead==NULL||pHead->next==NULL||pHead->next->next==NULL)
            return NULL;
        ListNode* pFast=pHead->next->next;
        ListNode* pSlow=pHead->next;
        while(pFast!=pSlow)
        {
            pFast=pFast->next->next;
            pSlow=pSlow->next;
            if(pFast->next==NULL||pFast->next==NULL)
                return NULL;
        }
        pFast=pHead;
        while(pFast!=pSlow)
        {
            pFast=pFast->next;
            pSlow=pSlow->next;
        }
        return pFast;
    }
};