题目描述

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

思路

快慢指针思想

• 设置一个快指针，一个慢指针，快指针一次走一步，慢指针一次走两步；
• 如果快指针走到了空指针，那么证明这个链表没有环；
• 如果快慢指针相遇了，表示有环
• 然后快指针回到头结点，两个指针同时走，每次都走一步
• 再次相遇时的节点就是入环节点
  需要注意的点：
  (1) 第一步就要判断头指针是不是空指针
  (2) 在这里我一开始只判断了头指针是不是空指针，但是有个问题，我在一开始定义的时候pFast=pHead->next->next的时候，如果链表这时候只有1个节点的话，那么这句话就会报错，所以还需要判断pHead->next是否为空，如果为空(也就是只有一个节点)，也返回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)
            return NULL;
        ListNode* pFast=pHead->next->next;  //快指针每次走两步
        ListNode* pSlow=pHead->next;  //慢指针每次走一步
        while(pFast!=pSlow)
        {
            if(pFast==NULL)  //如果快指针先走到了NULL，说明没有环，输出NULL
                return NULL;
            pFast=pFast->next->next;
            pSlow=pSlow->next;
        }
        pFast=pHead;  //快指针回到起点
        while(pFast!=pSlow)
        {
            pFast=pFast->next;   //同时走，每次都走一步
            pSlow=pSlow->next;
        }
        return pSlow;
    }
};