例题-链表中环的入口节点

题目描述

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

原理

如上图所示为模拟的一个链表环。

1. 找环中相汇点。分别用fast，slow指向链表头部，slow每次走一步，fast每次走二步，直到fast==slow找到在环中的相汇点。
2. 找环的入口。接上步，当fast==slow时，fast所经过节点数为2x,slow所经过节点数为x,设环中有n个节点，fast比slow多走r圈有2x=rn+x; x=rn;（r为圈数，n为一圈的结点数）
3. 可以看出slow实际走了多个环的步数，再让fast指向链表头部，slow位置不变
4. 假设链表开头到环接口的距离是y，那么x-y表示slow指针走过的除链表开头y在环中走过的距离，那么slow再走y步，此时fast结点与slow结点相遇，fast == slow ，x-y+y=x = rn，即此时slow指向环的入口

代码实现

struct ListNode
{
	int val;
	struct ListNode* next;
	ListNode(int x, ListNode* ptr = nullptr) :
		val(x), next(ptr)
		{}
};

ListNode* EntryNodeOfLoop(ListNode* pHead) 
{//入口找到节点
	ListNode* fast = pHead;
	ListNode* slow = pHead;
	while (fast != nullptr && fast->next != nullptr)
	{
		fast = fast->next->next;
		slow = slow->next;
		if (fast == slow)
		{
			fast = pHead;
			while (fast != slow) 
			{
				fast = fast->next;
				slow = slow->next;
			}
			return fast;
		}
	}
	return nullptr;
}