环形链表问题

题目描述：

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目思路：

1对于链表是否有环问题的判断。

两个指针什么情况下会相遇

定义两个指针，分别为快指针和慢指针。快慢指针同时从head开始向后移动。fast一次走两步，slow一次走一步，那么在fast或者fast->next不是尾结点的时候，fast和slow相交的话，就是有环的。

证明：由于快慢指针存在一个速度差，慢指针到达环的入口的时候，快指针已经进入了环并且走了一段距离。这时候就可以看作是快指针在追慢指针。由于快慢指针的速度差始终是1，因此每追一次，快慢指针的距离就缩小1，最后一定可以追上。

拓展：如果快指针一次走3步，慢指针一次走1步，那么快慢指针会相遇嘛？

思考：不一定会相遇。理由如下：快指针每次比慢指针多走两步，也就是说快慢指针之间的距离每次缩小2.假设如果入环的时候，快慢指针之间的距离相差N。如果N是奇数，那么N的变化如下：N,N-2,N-4,......,1,-1.

假设c为环的大小，-1表示的是快慢指针之间相差的距离是c-1.这时候快慢指针能否相遇就要思考c是奇数还是偶数了。如果c-1是奇数，c为偶数，那么快慢指针就会一直错过不会相遇；如果c-1是偶数，c是奇数，那么快慢指针就会相遇。

因此，如果快指针每次走3步，慢指针一次走1步的话，两个指针不一定会相遇。

所以，要想快慢指着相遇的话，他们之间的速度差需要保持1，那么就假设快指针每次走2步，慢指针每次走1步

在快慢指针运动的过程中，快慢指针之间存在一个怎样的关系呢？

 因为fast与slow的速度差始终是1，因此最开始的时候快慢指针最多差1圈。当慢指针进环的时候，必定只走了L+X就会被快指针追上。快指针走的路程是L+X+N*C(N为圈数，L为进环前的距离，X为快慢指针相遇的结点到入环处的距离，C为环的大小）。

由于快指针始终是慢指针的两倍，因此得到等式：2（L+X）=L+X+N*C，化简，变形，得

                                                       L=(N-1)*C+(C-X)

此时head和meet开始走，当head与meet相遇的时候，就是环的入口点。

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*slow=head;
    struct ListNode*fast=head;
    while(fast&&fast->next)
    {
       slow=slow->next;
       fast=fast->next->next;

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