快慢指针寻找环形链表入环节点

142. 环形链表 II - 力扣（LeetCode）

在寻找节点之前我们要知道一个公式L=（N-1）*C+（C-X）.

 

在上篇文章中我们可以知道，只要快指针和慢指针相遇了，就表示这个链表带环，而且我们可以知道相遇的点meet，在上图中就是4。 此时slow走的路程就是L+X，fast所走的路程就是L+N*C+X (N>=1，N表示在slow进环之前fast在环内转了N圈）。

因为快指针所走的距离是慢指针的二倍，因此我们能得出一个等式2*(L+X)=L+N*C+X，由这个等式可以推导出 L=N*C-X，即L=（N-1）*C+（C-X）。这时我们再建立一个head指针从头开始走，当走了C-X步后，meet正好走到入环节点的位置，head剩下的路程就是N*C了（N>=0），因此meet与head相遇的点就是入环的节点。

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast=head;
    struct ListNode *slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
        struct ListNode *meet=slow;
        while(meet!=head)
        {
            head=head->next;
            meet=meet->next;
        }
        return meet;
        }
    }
    return NULL;
}