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

运用双指针求解，快指针和慢指针，快指针一次移动两个结点，慢指针一次移动一个结点。

1、如果链表中有环结构，先用双指针找到环内的结点；

2、再将其中一个指针移动到头结点，两个结点同时每次移动一个结点，下次相遇时就是环的入口结点

时间复杂度：o(n)

空间复杂度：o(1)

class Solution {
  public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        //特殊情况处理
        if (pHead == nullptr || pHead->next == nullptr)
            return nullptr;

        ListNode* slow = pHead;
        ListNode* fast = pHead;
        ListNode* pnode = nullptr;
		//如果链表中有环结构，先用双指针找到环内的结点
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                pnode = slow;
                break;
            }    
        }
	  	//得到环的入口结点
        if (pnode != nullptr) {
            while (pHead != pnode) {
                pHead = pHead->next;
                pnode = pnode->next;
            }
            return pnode;
        } else {
            return nullptr;
        }
    }
};