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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* fast = pHead;
        if (fast == nullptr) return nullptr;
        fast = fast->next;
        if (fast == nullptr) return nullptr;
        fast = fast->next;
        ListNode* slow = pHead->next;

        while (slow != fast) {
            if (fast == nullptr) return nullptr;
            fast = fast->next;
            if (fast == nullptr) return nullptr;
            fast = fast->next;
            slow = slow->next;
        }
        
        fast = pHead;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

输入理解：{1,2},{3,4,5}表示环的入口在3，{1,2,3,4,5}是一个单链表，无环

解法：快慢指针，leetcode有原题，思路比较好理解

但写代码需要注意一点，也是快慢指针写法的点

一个模板的伪代码：（在循环外，先 移动一次fast和slow即可）

ListNode *fast, *slow;

if (root != nullptr && root->next->next != nullptr) fast = root->next->next;

slow = root->next;

while (slow != fast) { /**/}