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

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

        return slow;
    }
};

记住递推过程：2（X+Y） = X+Y+2*（Z+Y），其中X是从头结点到入口的距离，Y是从入口到相遇位置的距离，Z是环中减去Y的长度。