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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) 
    {
        ListNode* fast=pHead;
        ListNode* slow=pHead;
        while(fast!=nullptr&&fast->next!=nullptr)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            {
                ListNode* p=fast;
                ListNode* q=pHead;
                if(p==q)return p;//如果只有一个节点的环，需要直接返回
                while(p!=nullptr)
                {
                    p=p->next;
                    q=q->next;
                    if(p==q)return q;
                }
            }
        }
        return nullptr;
    }
};

通过双指针的另一种应用快慢指针，可以轻松解决，定义一个快指针fast，每次跳跃两个节点，定义一个慢指针slow，每次跳跃一个节点，两个指针从同一个位置开始遍历，如果最后两个指针相遇了，就说明该链表有环，如果fast直接等于nullptr了，那么就是没有环。