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

解题步骤：
1.使用快慢指针，找到在环中的相遇结点（快指针一下走2步，慢指针一下走一步）
2.在环中走一圈，统计环中的结点个数n（在环中走，不会走出去，再次回到初始结点为一圈）
3.定义两个指针，一个指针先走n步，另一个指针指向头结点，
--然后一步步的往下走，相遇时，走了n步的指针，刚好走了一圈，也就是相遇结点为环入口

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    /*
    解题步骤：
    1.使用快慢指针，找到在环中的相遇结点
    2.在环中走一圈，统计环中的结点个数n
    3.定义两个指针，一个指针先走n步，另一个指针指向头结点，
    --然后一步步的往下走，相遇时，走了n步的指针，刚好走了一圈，也就是相遇结点为环入口
    */
    //先找到相遇的节点
    ListNode* FindMeetNode(ListNode* pHead){
        if(pHead == NULL){
            return NULL;
        }
        ListNode* slow = pHead->next;
        if(slow == NULL){
            return NULL;
        }
        ListNode* fast = slow->next;
        while(fast != NULL && slow != NULL){
            if(fast == slow){
                return slow;
            }
            slow = slow->next;
            fast = fast->next;
            if(fast != NULL){
                fast = fast->next;
            }
        }
        return NULL;
    }

    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* meetNode = FindMeetNode(pHead);
        if(meetNode == NULL){
            return NULL;
        }
        ListNode* p = meetNode->next;
        int count = 1;
        //算出环的结点数
        while(p != meetNode){
            count++;
            p = p->next;
        }
        //算出环入口
        p = pHead;
        ListNode* pt = pHead;
        //先走count步
        while(count--){
            p = p->next;
        }
        while(pt != p){
            pt = pt->next;
            p = p->next;
        }
        return p;

    }
};