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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    // write code here
    struct ListNode* kuai = pHead;
    struct ListNode* man = pHead;
    struct ListNode* meet = pHead;
    while (kuai && kuai->next) {
        kuai = kuai->next->next;
        man = man->next;
        if(kuai==man){
            while(meet != man){
                meet = meet->next;
                man = man->next;
            }
            return meet;
        }
    }
    return NULL;
}

思路：

1. 设置快慢指针，假如有环，他们最后一定相遇在环中。
2. 两个指针相遇后，让两个指针分别从链表头和相遇点重新出发，每次走一步，最后一定相遇于环入口。