【数据结构初阶】详解 环形链表：链表的带环问题（判断是否带环、环形链表的入口点）

一、链表的带环问题

1.1、判断链表是否带环（力扣 141.环形链表）

题目：给你一个链表的头节点 head ，判断链表中是否有环。如果链表中存在环 ，则返回 true 。 否则，返回 false 。

带环：链表的尾节点的next指向链表中的任一节点。
环形链表如下：

方法：快慢指针（追击相遇问题）
快指针：fast，慢指针：slow
令fast的速度是slow的2倍，那么在相同的时间内，fast走过的路程是slow的2倍。
故可得：

结论：若带环，快指针fast一定能追上slow，即fast与slow一定会相遇。
若不带环，fast先到达尾节点，结束，此时fast一定在尾，slow在中间，不会相遇。

1.2 、证明：为什么带环时快慢指针一定相遇？

当二者间距离变为0时，fast与slow相遇。

如上图所示，随slow与fast的移动，二者间的距离一定会变为0，即fast与slow一定会相遇。

1.3、证明：当slow走1步，fast可走3/4/5步（fast的速度是slow的3/4/5倍）吗？

首先要明白一点：速度的倍数关系存在的根本原因是为了判断二者在该速度下一定能相遇。来作为判断是否带环的区分。所以如果能相遇（追上），就可以作为链表带环的判断条件。

1.3.1、slow走1步，fast走3步

由上图可知：
1、当N为偶数时，N最终能够变化为0，一定能相遇。
2、当N为奇数时，设环的周长为C，距离变化为-1时，即fast快slow一步，那么第二轮追击时二者间距为N=C-1，那么若C-1为偶数，第二轮可以追上；若C-1为奇数，第二轮追不上。
那么由上追不上的情况只有N为奇数且C-1为奇数。
但是 由fast的总路程我们可以得到以下等式： 得到等式 2L=（x+1）*C-N，等式左边为偶数，当N为奇数， C-1为奇数即C为偶数时，
偶数-奇数不等于偶数，故此时等式不成立，所以不存在N为奇数，C-1为奇数的情况。

结论：
当N为偶数时，第一轮就能追上
当N为奇数时，若C-1为偶数，第二轮能追上
而N为奇数，C-1为奇数的情况不存在
所以当slow走1步，fast走3步时一定可以追上。

1.3.2、slow走1步，fast走4步

相当于slow每走1步，二者的间距减少3

1.4、代码

这里的循环条件是 fast不为空且fast->next不为空。
原因：NULL不能再进行解引用操作。
若fast为空，那么在fast=fast->next->next中，fast->next进行了解引用，程序报错。
若fast->next为空，那么在fast=fast->next->next中，fast->next->next进行了解引用，程序报错。

bool hasCycle(struct ListNode *head) {
    struct ListNode *fast=head, *slow=head;
    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(fast == slow)
            return true;
    }
    return false;
}

2.1、判断环形链表的入口点（力扣 142.环形链表2）

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

2.1.1、方法一：相遇

head为头指针，指向链表的头结点。
meet为相遇指针，指向fast与slow相遇的位置。

结论：head与meet同时走，一定会在入口点相遇。
证明：
由上可得，本题一定要使用快慢指针的追击相遇，那么fast与slow有速度差，根据1.1的证明，我们还是使用速度为二倍关系比较容易。
即 slow走1步，fast走2步。

2.1.2、方法二：链表的相交

找到入口点后，再把环形链表还原即可。

2.2、代码

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

二、谢谢观看！