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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
 
struct ListNode *findCycleNode(struct ListNode* Node1, struct ListNode* Node2, struct ListNode* pHead);//  成员函数声明

struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) //经典快慢指针
{
    if (pHead == NULL) return NULL;
    
    struct ListNode *slow = pHead;
    struct ListNode *fast = pHead;
    while(slow != NULL && fast->next != NULL && fast->next->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            struct ListNode *cycleNode = findCycleNode(slow, fast, pHead);//判断有环则寻找环入口节点
            return cycleNode;
        }
        else 
        {
            continue;
        }
    }
    
    return NULL;
}

struct ListNode *findCycleNode(struct ListNode* Node1, struct ListNode* Node2, struct ListNode* pHead)
{
    Node2 = pHead;
    while(Node1 != Node2)
    {
        Node1 = Node1->next;
        Node2 = Node2->next;
    }//确定有环才会进入这个循环，因此一定会出现Node1 == Node2的情况，不会出现死循环。
    
    return Node1;
}
/*分别定义快指针fast、慢指针slow，初始时两指针均指定链表首结点；快指针每次移动两个结点，慢指针每次移动一个结点；

1. 若链表有环则指针fast、slow一定会相遇（来源数学龟兔赛跑问题），否则快指针为空时返回nullptr；

2. 当fast、slow第一次相遇时，假设其相遇于结点I，设结点I距离入口结点G的距离为d，则此时快指针fast移动了2x = a + d + mR (m为整数)、慢指针slow移动了x = a + d + nR (n为整数)；(R为环的长度）

3. 易得a + d = (m - 2n)R；

4. 此时将快指针fast重新指向链表首结点，让fast、slow同速运动，则当fast再次移动a距离后，fast指针移动的距离为a ，slow指针移动的距离为 a + d + nR + a = a + (m - n)R = a + kR(k为整数)；易知此时fast、slow重新相遇且相遇结点即为链表环入口结点；*/