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

根据两个结论设置两个方法完成：

结论一：设置快慢两个指针，（V(p1) = 2 ，V(p2) = 1 ），当存在环时一定会相遇。

结论二：将两个相同速度(V(p) = 1)的指针从起始点和相遇点进行移动，最终的相遇点就是环入口。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */

    //相遇点
#include <stdio.h>
struct ListNode* FindEncounterNode(struct ListNode* pHead){
    struct ListNode* fast = pHead;
    struct ListNode* slow = pHead;
    struct ListNode* encount_point = NULL;
    while(fast!=NULL && fast->next!=NULL){
        fast = fast ->next->next;
        slow = slow->next;
        if(fast == slow){
            return encount_point = fast;
        }
    }
    return NULL;
} 
    //进入点
struct ListNode* FindEnterNode(struct ListNode* pHead1,struct ListNode* pHead2){
    struct ListNode* p1 = pHead1;
    struct ListNode* p2 = pHead2;
    struct ListNode* enter_point = NULL;
    while(p1!=p2){
        p1 = p1->next;
        p2 = p2->next;
    }
    enter_point = p1;
    return enter_point;
}

struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    // write code here
    struct ListNode* p_encounter = pHead;
    struct ListNode* p_resul = pHead;
    //寻找相遇点
    p_encounter = FindEncounterNode(p_encounter);
    if (!p_encounter) return p_encounter;
    //寻找进入点
    p_resul = FindEnterNode(p_resul,p_encounter);
    return p_resul;
}