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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pHead ListNode类
 * @return ListNode类
 */
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    //思路
    //判断是否有环
    //在有环的情况下，设【头结点->环入口】距离为X，【环入口->相遇结点】距离为Y，【相遇结点->环入口】距离为Z
    //相遇时，slow指针共走了X+Y，fast则为2X+2Y（slow的两倍，已经绕环一圈多了）。
    //则有，Z = 2X + 2Y - 2Y - X = X，即Z = X，【相遇结点->环入口】等于【头结点->环入口】
    //因此从相遇点和头结点开始设置指针遍历，二者相同时为环入口

    struct ListNode* fast = pHead;
    struct ListNode* slow = pHead;

    if (pHead == NULL) {
        return NULL;
    }

    while ((slow != NULL) && (fast != NULL) && (fast->next != NULL)) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = pHead;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return NULL;
}