链表带环问题

总结：链表带环问题

追击问题：fast追上slow就带环

1为什么一定会相遇，有没有可能会错过？

2slow一次走1步，fast走3步，4步，5步可以吗？请证明。

假设slow进环的时候，fast跟slow的距离是N，fast追击slow距离变短。

假设slow一次走一步，fast一次走三步，假设fast和slow之间的距离是N。

相当于一次追两步，那么下一次两指针之间的距离就是N-2。

如果是奇数和偶数，会有两种不同的结果：

-1就是两个指针会错过，进入新一轮的追击，距离变成C-1（C是环的长度）：

若C-1是偶数，那么追得上，若C-1是奇数，那么又再一次追不上了，陷入死循环。

总结：

1如果N是偶数，那么下一轮就追上了

2如果N是奇数，第一轮错过

C-1为偶，追上

C-1为奇，陷入死循环，永远追不上

假设slow进环时，slow和fast之间的距离是N。假设fast已经在环里面转了x圈。

slow走的距离：L

fast走的距离：L+x*C+（C-N）

fast走的距离是x的三倍，3L=L+X*C+(C-N)。

2L=（X+1）*C-N

偶数=（X+1）*偶数-奇数

这个条件不可能同时存在

永远追不上的条件是：同时存在N是奇数且C是偶数，那么永远追不上。

所以不可能永远追不上

N是偶数，C也是偶数

N是奇数，C也是奇数

结论N偶数第一轮追上

N奇数，第一轮追不上，下一轮就追上了

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

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

相遇时slow走的路程：L+N

(慢指针有没有可能在环里走了好多圈呢，没有可能，如果走了好多圈，fast一定会超过slow

fast走的路程：L+x*C+N

2*（L+N）=L+x*C+N

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