链表中的入口结点

---

题目描述

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

解题思路

判断一个链表是否含有环，可以使用快慢指针：

让pslow, pfast两个指针pslow = pslow->next，pfast = pfast->next->next，若两个指针相遇则说明此链表包含环，且相遇结点肯定在环内。

判断环的入口结点，也可以使用两个指针来实现：

两个指针P1, P2都指向链表的头结点。然后根据环中结点的个数（可以通过快慢指针得到的相遇结点为起点，再循环一圈同时记录环中结点个数），让其中一个指针，假如是P1先移动n个位置，然后P2在开始与指针P1一起移动（每次移动一个结点），当两个指针相遇时的结点，即为环的入口结点。

代码

struct ListNode
{
    int val;
    struct ListNode* next;
    ListNode (int x): val(x), next(NULL) {}
};
class Solution
{
public:
    ListNode* EntryNodeOfLoop (ListNode* pHead)
    {
        if (pHead == NULL)
            return NULL;
        
        // 通过快慢指针寻找相遇结点
        ListNode* meetNode = meetingNode(pHead);
        if (meetNode == NULL)
            return NULL;
        // 通过相遇结点，得出环中的结点总数
        ListNode* pNode1 = meetNode;
        int count = 1;
        while (pNode1->next != meetNode)
        {
            pNode1 = pNode1->next;
            count++;
        }
        
        // 通过指针 p1先走n个结点 ,p2再一同开始移动，从而找到环的入口结点
        pNode1 = pHead;
        for (int i = 0; i < count; i++)
            pNode1 = pNode1->next;
        ListNode* pNode2 = pHead;
        while (pNode1 != pNode2)
        {
            pNode1 = pNode1->next;
            pNode2 = pNode2->next;
        }
        return pNode1;
    }
    
private:
    ListNode* meetingNode (ListNode* pHead)
    {
        ListNode* slowNode = pHead->next;
        if (slowNode == NULL)
            return NULL;
        ListNode* fastNode = slowNode->next;
        while (slowNode != NULL && fastNode != NULL)
        {
            if (slowNode == fastNode)
                return fastNode;
            slowNode = slowNode->next;
            fastNode = fastNode->next;
            if (fastNode != NULL)
                fastNode = fastNode->next;
        }
        return NULL;
    }
};

参考博文链接：https://cuijiahua.com/blog/2018/01/basis_55.html