判断环形链表及寻找入环口问题详解

妖狐艹你老母 2023-09-26 18:37 4阅读 0赞

![8d23f7b2cb634ad7913eed571da13a9d.gif][]

> **文章目录**
> 
> 一、判断环形链表
> 
> 1、1 题目描述
> 
> 1、2 题解详细思路与解答
> 
> 二、找环形链表的入环点
> 
> 2、1 题目描述
> 
> 2、2 题解思路
> 
> 2、2、1 为什么快指针每次走两步，慢指针走一步可以？
> 
> 2、2、2 快指针一次走3步，走4步，...n步行吗？
> 
> 2、2、3 是否能够相遇关键因素
> 
> 2、3 找入环点
> 
>  三、总结
> 
> --------------------
> 
> 链表在面试和笔试中都是十分常见的问题。本篇文章会简述到**判断环形链表**和**返回环形链表的入环点**。其中有较多的细节，本篇文章会详细解释。

## 一、判断环形链表 ##

### 1、1 题目描述 ###

> **题目来源：**Leetcode
> 
> **题目难度：**简单
> 
> **题目描述：**给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
> 
> 注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。
> 
> ![1b158af4ba014348acfedc398e7e683c.png][]
> 
> 题目数据 **保证** 整个链式结构中不存在环。
> 
>  **注意**，函数返回结果后，链表必须 **保持其原始结构** 。

### 1、2 题解详细思路与解答 ###

> 我们发现，**环形链表是不能够随对其进行遍历的，如果不加任何操作，会很容易造成死循环**。那怎么判断是否有环呢？我们不妨用一下追赶问题去考虑一下。也就是**快慢指针**。如果有环的话，快指针会先走进环内，并且一直在环内进行循环。慢指针会后进入环内。当两个指针都进入环内时，就成为了一个追击问题了。我们不妨设置快指针一次走两个节点，慢指针一次走一个节点，**两个指针都进入环内就成为了快指针追击慢指针的情况**了。此时如果有环一定会相遇。
> 
> 我们先看代码的实现：

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

> 上述代码中，如果没有环，**当链表中节点个数为奇数时，fast->next 为空时是截至条件。当链表的节点个数为偶数时，fast 为空时是截至条件**。

## 二、找环形链表的入环点 ##

### 2、1 题目描述 ###

> **题目来源：**Leetcode
> 
> **题目难度：**中等
> 
> **题目描述：**给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。
> 
> ![ff32bf09358c4d78be767b61d4df1831.png][]
> 
> ![10f189a7ceb9467a96d21b45d87e4a81.png][]

### 2、2 题解思路 ###

> 当我们在做判断环形链表时，我们设置的快指针一次走两个节点，慢指针一次走一个节点。为什么要这样设置呢？那么快指针一次走三步、四步……呢？这其中到底与什么有关呢？我们继续往下分析。

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

>  假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚 
> 
> 进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。 此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
> 
>  我们发现上述重点是在分析的相对速度。即我们可以看成慢指针没有走，快指针每次走一步在追赶，不会错过的，一定会追上并且相遇的。

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

>  为什么slow走1步，fast走x步(X>=3)，他们会相遇?会不会错过?请证明。我们**先来看快指针一次走3步，慢指针一次走1步的情况**。
> 
>  假设slow进环的时候fast和slow之间距离是N。slow进环以后，fast开始追击slow，slow每走1步，fast走3步，他们之间的距离缩小2。假设fast和slow之间的距离为偶数，那么每次距离缩减2，那么一定会追上且会相遇。假设fast和slow之间的距离为奇数，第**一圈fast会超过slow，会追上但不会相遇**。那么**第二圈的时候，它们之间的距离变成了N-1。距离就变成了偶数了，第二圈会追上且相遇**。

> 那么**快指针一次走4步，慢指针一次走1步的情况呢**？我们再来分析一波。
> 
>  假设slow进环的时候fast和slow之间距离是N。slow进环以后，fast开始追击slow，slow每走1步，fast走4步，他们之间的距离缩小3。假设N是3的倍数，那么每次距离缩小3，第一圈就会追上并且相遇。那么如果N不是3的倍数，是N%3为2，第一圈并不会相遇，第二圈距离会变成N-1。(N-1)%3为1，第二圈又不会相遇。第三圈距离会变成N-1-2，我们发下减去3相当于没减。会一直循环下去，并不会相遇。当N%3为1时，与上述中的一种情况一样，也会陷入死循环。所以快指针一次走4步，慢指针一次走1步的情况是不行的。![77a570482e254756b8d485d4665f63f5.png][]

#### 2、2、3 是否能够相遇关键因素 ####

> 通过上面的两种情况的分析，发现快慢指针能否相遇，关键是有两个因素：**慢指针进环时与快指针之间的距离**和**两者的相对速度**。那怎么找入环点呢？

### 2、3 找入环点 ###

> 我们接着分析：
> 
> 我们在这里不妨分析一下快慢指针的整个过程，如下图：
> 
> ![67418266be23473fa515f9a1781425d4.png][]
> 
> 我们就以快指针每次走两步，慢指针走一步的情况进行分析。那么**当两个指针相遇时，slow一定时走的环形的第一圈**。因为我们假如slow在环内走了一圈多，那么fast最少走了两圈，因为相对速度为1，追上即相遇，当fast走到两圈多的情况下早就相遇过，故slow走一圈多不成立。但是在slow入环之前，fast已经在环内走了很多圈（我们假设已经走了n圈，n可能等于1，2……）。故**相遇时我们可以列出两者的距离等式：2\*（L+X）=L+n\*C+X**。我们在对等式进行变换：**L=n\*C-X**。我们在对等式进行分析：L为入环前的距离，**n\*C-X=（n-1）\*C + C-X**。这里我们这能算出C环的长度，其他的都是未知数。这个**L=（n-1）\*C + C-X**等式也就意味着，在有环的情况下，**一个指针从起始点走，一个指针从相遇点走**，从相遇点走的指针可能在环内走了很多圈，也有可能一圈也没有，**那么两个点再次相遇的位置即为入环点的位置**了。我们再看代码：

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

## 三、总结 ##

> 上述的问题在**面试中很常见**，问怎么看是否有环，为什么快指针每次走两步，慢指针走一步可以？快指针一次走3步，走4步，...n步行吗？还有一个就是找入环点的位置。希望本编文章会对你有所帮助，可以很好的解决这些问题。一定要搞清楚细节问题，不要只记结论，否则会吃大亏。
> 
> 本篇文章的讲解就到这里，希望以上内容会对你有所帮助，感谢观看ovo~

[8d23f7b2cb634ad7913eed571da13a9d.gif]: https://img-blog.csdnimg.cn/8d23f7b2cb634ad7913eed571da13a9d.gif
[1b158af4ba014348acfedc398e7e683c.png]: https://img-blog.csdnimg.cn/1b158af4ba014348acfedc398e7e683c.png
[ff32bf09358c4d78be767b61d4df1831.png]: https://img-blog.csdnimg.cn/ff32bf09358c4d78be767b61d4df1831.png
[10f189a7ceb9467a96d21b45d87e4a81.png]: https://img-blog.csdnimg.cn/10f189a7ceb9467a96d21b45d87e4a81.png
[77a570482e254756b8d485d4665f63f5.png]: https://img-blog.csdnimg.cn/77a570482e254756b8d485d4665f63f5.png
[67418266be23473fa515f9a1781425d4.png]: https://img-blog.csdnimg.cn/67418266be23473fa515f9a1781425d4.png