剑指offer（C++）——链表中环的入口结点

小鱼儿 2022-06-16 21:15 173阅读 0赞

## 题目描述 ##

一个链表中包含环，请找出该链表的环的入口结点

struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :val(x), next(NULL) {}
    };
    
    /*思路：设置两个指针p1和p2，如果链表中有n个结点，指针p1先向前移动n个结点，然后两个指针以相同速度向前移动，当两个指针相遇的结点就是环的入口结点。
    如何统计环中结点个数n：设置一快一慢两个指针pSlow和pFast，如果链表中有环，两指针必定在环中某个结点出相遇。从此结点开始计数，当再次到达此结点时，就可以得到环中结点数*/
    class Solution {
    public:
    	ListNode* EntryNodeOfLoop(ListNode* pHead)
    	{
    		if (pHead == NULL)
    			return NULL;
    		ListNode* meetingNode = MeetingNode(pHead);         //找到环中的一个结点
    		if (meetingNode == NULL)
    			return NULL;
    		int countNode = 1;
    		ListNode* pNode1 = meetingNode;
    		while (pNode1->next != meetingNode)                         //统计环中结点个数
    		{
    			pNode1 = pNode1->next;
    			++countNode;
    		}
    		pNode1 = pHead;
    		for (int i = 0; i < countNode;i++)
    			pNode1 = pNode1->next;
    		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;
    		ListNode* pFast = pSlow->next;
    		if (pFast == NULL)
    			return NULL;
    		while (pSlow != NULL&&pFast != NULL)
    		{
    			if (pFast == pSlow)
    				return pFast;
    			pSlow = pSlow->next;
    			pFast = pFast->next;
    			if (pFast != NULL)
    				pFast = pFast->next;
    		}
    		return NULL;
    	}
    };