🎁个人主页：我们的五年

🔍系列专栏：数据结构

🌷追光的人，终会万丈光芒

 

 前言：

链表的带环问题在链表中是一类比较难的问题，它对我们的思维有一个比较高的要求，但是这一类问题分析起来也是很有趣的，下面我就给大家讲一下链表的带环问题，并且带上几个例题进行分析。

喜欢的铁子们可以点点关注，感谢大家的支持。

🏝1.链表的分类：

●根据链表，单向，双向，带头，不带头，循环，不循环，可以把链表分成八种。虽然说有八种链表，但是常用的只有：不带头单向不循环链表，带头双向循环链表。

●但是今天我们要看的是不带头单向不循环，但是内部带环的问题。

🏝2.判断链表是否带环？

【LeetCode】第141题-链接：https://leetcode.cn/problems/linked-list-cycle/description/

 🏜问题描述：

 

 🏜实现代码：

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

 typedef struct ListNode ListNode;

bool hasCycle(struct ListNode *head) {

    ListNode* fast=head;

    ListNode* slow=head;

    while(fast&&fast->next)

    {

        fast=fast->next->next;

        slow=slow->next;

        if(fast==slow)

            return true;

    }

    return false;

}

🏜问题分析：

1.快慢指针都从头开始走，慢指针一次走一步，快指针一次走两步。

2.当fast进环的时候，slow还在环外。

3.当slow金环的时候，fast在环中的某个位置。也就是说，fast和slow差了N个位置，当fast和slow都进环的时候，就变成了追击问题。

4.slow每次走一步，fast每次走两步，也就是fast去追slow，把slow看成静止的，fast就一次往前面走一步，所以fast一定可以追上slow。

🏝3.如果fast一次走三步，slow一次走一步，一定可以追上吗？

这里先给出答案：一定可以追上！

当slow刚刚进环的时候，fast在环的某个位置，此时fast开始追击slow，还是把slow看成静止的，fast每次往相对于slow追击两步。

开始时，slow与fast相差N

1.当N为偶数时：

因为每次fast走三步，slow走一步。也就是N每次-2。因为N为偶数，所以是一定可以追上的。

2.当N为奇数，环的周长为C为奇数：

因为N每次都是-2，所以第一次追的时候fast和slow会错过，fast比slow快出了一步。

此时环的周长C为奇数，那么此时fast和slow相差为C-1为偶数，那么就回到第一种情况。

3.N为奇数，C为偶数，根据情况2，fast追完一圈，fast和slow相差的距离为奇数，所以fast和slow会一直错过，但是这种情况真的存在吗？

先来看看这个等式：

slow刚刚进环时：

slow走过的路程为：L

fast走过的路程为：L+k*C+C-N

因为fast的速度是slow的三倍，所以有3*L=L+k*C+C-N。

2*L=k*C+C-N

等式左边：偶数

等式右边：情况3时的情况是：C为偶数，N为奇数，k*C为偶数，C-N为奇数，所以等式右边为奇数

所以这种情况是不存在的！！！

代码分析：fast一次走三步，slow一次走一步

 typedef struct ListNode ListNode;

bool hasCycle(struct ListNode *head) {

    ListNode* fast=head;

    ListNode* slow=head;

    while(fast&&fast->next&&fast->next->next)

    {

        fast=fast->next->next->next;

        slow=slow->next;

        if(fast==slow)

            return true;

    }

    return false;

}

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