题解 | #链表中环的入口结点#

快慢指针法

快指针速度是慢指针速度的2倍。如图所示，设快慢指针相遇在C点，相遇时快指针走过2S，则慢指针走过S。

慢指针走了S=a+b

快指针走了2S=a+b+n(b+c)

可得a=(n-1)(b+c)+c

也就是说a等于若干圆周加上c。那让两个指针同时在A点和C点出发，必然相遇在B点（入口）

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
		ListNode* fast = pHead;		
		ListNode* slow = pHead;
		
		while (fast && fast->next)
		{
			slow = slow->next;
			fast = fast->next->next;
			
			if (slow == fast)
			{
				break;
			}
		}
		
		if (fast == NULL || fast->next == NULL)
		{
			return NULL;
		}
		
		slow = pHead;
		while (slow != fast)
		{
			slow = slow->next;
			fast = fast->next;
		}
		
		return slow;
    }
};