【链表】：链表的带环问题

前言： 链表的带环问题在链表中是一类比较难的问题，它对我们的思维有一个比较高的要求，但是这一类问题分析起来也是很有趣的，下面我就给大家讲一下链表的带环问题，并且带上几个例题进行分析。 喜欢的铁子们可以点点关注，感谢大家的支持。

🏝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;
}