链表中环的入口结点

题目描述

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

思路

1. 判断链表中是否存在环。
2. 判断环中结点个数。
3. 计算链表中环的入口结点。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        //1.定义两个指针，一个指针一次走一步，一个指针一次走两步,后判断链表是否有环。
        ListNode*meetingNode = MeetingNode(pHead);
        if (meetingNode == NULL) {
            return NULL;
        }
        //2.有环，确定环的数量
        int nodeslnLoop = 1;
        //当前结点已经在环上了所以 nodeslnloop=1
        ListNode *pNode1 = meetingNode;
        //直接用结点比较
        while (pNode1->next!= meetingNode)
        {
            pNode1 = pNode1->next;
            nodeslnLoop++;
        }
        //3.确定环的入口结点
        //先移动pNode1,次数为环中结点数目
        pNode1 = pHead;
        for (int i = 0; i <nodeslnLoop; i++)
        {
            pNode1 = pNode1->next;
        }
        //再同时移动pNode1和pNode2
        ListNode *pNode2 = pHead;
        while (pNode1!=pNode2)
        {
            pNode1 = pNode1->next;
            pNode2 = pNode2->next;

        }
        return pNode1;
    }
    ListNode* MeetingNode(ListNode *pHead) {
        if (pHead == NULL) {
            return NULL;
        }
        //慢指针一次走一步
        ListNode *pSlow = pHead->next;
        if (pSlow == NULL) {
            return NULL;
        }
        //快指针走两步
        ListNode *pFast = pSlow->next;
        while (pFast!= NULL&&pSlow!= NULL)
        {
            //指针相遇
            if (pFast == pSlow) {
                return pFast;
            }
            //慢指针走一步
            pSlow = pSlow->next;
            //快指针走两步
            pFast = pFast->next;
            if (pFast != NULL) {
                pFast = pFast->next;
            }
        }
        return NULL;
    }
};