【数据结构】C语言算法练习题——利用“快慢指针”去判断一个链表中是否带环_快慢指针判断链表是否有环

题目链接：

力扣https://leetcode.cn/problems/linked-list-cycle/submissions/

解题思路：

1. 带环链表不能遍历，否则会造成死循环

2. 定义俩个快慢指针，慢指针每次向后走一步，快指针每次向后走俩步。即快慢指针相差一步。

所以如果一个链表中存在环结构，

则快指针一定比慢指针先进入环结构，随着快指针进入环内运动循环，慢指针最终也会进入环内。

因为快慢指针均进入了一个环结构，所以不会遇到 NULL 指针，一直在循环。

这会使快慢指针最终会相遇，即指向的地址相同

而如果这个 单链表中 不存在环结构，则快指针最终会遇到 NULL 指针结束循环

这实际上是根据带环链表的结构特点去解题

3. 不带环结构的单链表需要考虑其结点的个数是奇数个还是偶数个

4. 【思考】：为什么快慢指针在环结构内最终一定会相遇？

为什么快指针每次走两步，慢指针走一步可以？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。

当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。

此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，

因此：在满指针走到一圈之前，

快指针肯定是可以追上慢指针的，即相遇

快指针一次走3步，走4步，...n步行吗？

不一定可行，即慢指针可能追得上快指针，也可能追不上

假设快指针一次走三步，慢指针一次走一步：

因为不知道环的长度是奇数还是偶数，如果环的长度是偶数，则最终会相遇，而如果环的长度为奇数，则会追不上

距离是 -1 意味着：快慢指针之间的距离 C（环的长度 ）- 1

所以当进入新的一次带环结构循环时，如果C - 1 为奇数则永远追不上，如果C - 1 为偶数，则会在

接下来的几次带环结构里的循环追上

参考代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) 
{
    struct ListNode *fast , *slow;
    slow = head;
    fast = head;
    while (fast && fast->next)//不带环结构的单链表的结点个数分奇数个和偶数个；
                              //存在偶数个结点时是 fast 走到 NULL
                              //存在奇数个结点时是 fast->next 走到 NULL
    {
        slow = slow->next;
        fast = fast->next->next;//比慢指针多走一步，每次向后行走俩步
        if (slow == fast)
        {
            return true;
        }
 
    }
 
    return false;
    
}

【题目变式】：

力扣https://leetcode.cn/problems/linked-list-cycle-ii/description/

解题思路：

要想找到链表开始入环的第一个结点，

设入环前的距离为 L ，假设链表中带环，所以当快慢指针在环内相遇时，设慢指针从开始入环处的

第一个结点开始到快慢指针相遇时 慢指针走过的距离为 X 

注意：

进入环内快指针追上慢指针所走过的距离不会超过环的长度

其理由是：

快指针每次走俩步，而慢指针每次走一步，它们之间相差一步，即它们不像相差3步或俩步一样，

可能会错过，

假设慢指针已经走了一圈的长度没有遇到快指针，

因为每次快指针都比慢指针多走一步，所以此时快指针已经走了俩圈，

而且因为每次都相差一步，所以不会跳过慢指针，即不可能遇不到已经走了一圈的慢指针

即要么快慢指针要么遇不到，要么遇到就是在一圈之内

参考代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode *slow,*fast;
    slow = 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;//meet与head同时向后走一步，注意与前面快慢指针所走步数的不同
            }
            return meet;
 
        }
    }
    
    return NULL;
}