LeetCode | 一探环形链表的奥秘【快慢双指针妙解BAT等大厂经典算法题】_leetcode快慢指针 第一圈

前言

本文总结了力扣141.环形链表|以及142.环形链表||这两道有关环形链表的求解方案，去求证链表是否带环已经如何找出入环口的结点。
有关环形链表，在BAT等大厂面试中均有出现，一般是属于中等难度的题，需掌握

一、题目描述

原题传送门

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

• 链表中节点的数目范围是 [0, 104]
• -105 <= Node.val <= 105
• pos 为 -1 或者链表中的一个 有效索引 。

二、思路分析与罗列

好，看完了题目描述，接下去我们来分析一下如何去求解这道题目

• 首先对于此题，首先你要考虑的一点是怎么去判断一个链表是否有环?
• 在一开始看题目的时候你可能想了很多的办法，但是当写代码的时候，发现又不对。有点同学就和我说：这不是很简单，搞一个指针，做一个遍历，若是若是这个指针又回到原来的交点，那不就是带环吗
• 那我只能说，这个同学没有读清楚题目，题目并没有告诉你这个环的入口在哪里，你怎么去判断这个遍历的指针走了一圈呢？所以这都是无稽之谈，我们应该通过画图来进行分析

• 从上述图中可以看到，我使用来一个叫做快慢指针，这其实是解决环形链表这种问题的最好手段，具体的思路就是让快慢指针同时遍历这个链表，快指针走两步，慢指针走一步，然后在不断遍历的过程中，若是两个指针重合了，说明链表带环，具体的证明我放在后面讲解
• 我们先来看一下快慢指针是如何遍历的

【牢记规则：快指针走两步，慢指针走一步】

• 好，通过上面的算法图示，相信你已经明白了快慢指针最后究竟是如何相遇的，这个光凭空想还真的不好想出来，但是我们画个图来分析一下，就非常地明确了。我们在下一模块来写写代码

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast, *slow;
        fast = slow = head;

        while(fast && fast->next)       //判断奇数和偶数个结点的情况
        {
            slow = slow->next;
            fast = fast->next->next;

            if(fast == slow)
                return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 可以看出，代码并不复杂，就是通过一个循环去让这两个快慢指针去遍历这个链表，若是它们相遇，则【return true】，若是循环遍历结束还是没有遇见，则说明链表不带环

三、证明：

1、【为何快指针每次走两步，慢指针走一步一定能相遇？】

• 相信在看完我上面的一些简略分析后有些小伙伴一定会疑惑为什么快指针每次走两步，慢指针每次走一步一定能相遇
• 首先我在这里做一个假设，就是当快指针已经入环，而慢指针刚好入环时，他们之间的距离相差N

• 然后此时缩小快慢指针的宏观移动距离，然后观察两个指针的移动的是否会改变他们之间的距离
• 首先记录下它们的第一次移动①

• 然后是第二次移动，继续计算它们之间的距离

• 于是我们可以得出来下面这个结论，快指针【fast】和慢指针【slow】在不断前进的过程中它们之间的距离是会不断缩短的，当它们之间的距离 = 0时，其实也就意味着它们相交了
• 其实快指针就是一个不断在追逐慢指针的一个过程

• 所以就可以证明这个结论——》【快指针每次走两步，慢指针走一步一定能相遇】

2、【快指针一次走3步，走4步，…n步行吗？】

• 接下去我们再来证明一个问题，刚才快指针一次是走两步，一定能追上，那现在当这个快指针一次走3步、走4步能不能追得上呢？我们一起来分析一下
• 情况有很多，我这里就拿【fast】走3步，【slow】走1步来进行一个证明

• 那根据我们上一个问题的证明，这依旧设【fast】在环中当【slow】刚进环时两者之间的距离为N，然后就可以得到两者在追击时它们之间的距离每次会缩短2，然后就可以去计算它们可不可能相遇
• 因为它们之间的距离每次缩短的长度是一致的，所以就需要看这个N的大小，也就是在环中【fast】和【slow】之间的距离，若是N为偶数，那最后它们之间的距离一定会减少到0，也就意味着相遇；若是N为奇数，那最后它们之间的距离一定会减少到-1，这就意味着【fast】追是追上【slow】，但是呢却刚好错过了，到达了它的前一位

• 我们来做一个模拟，此时当【fast】和【slow】快相遇时，它们继续行走

• OK，可以看到，它们确实是错过了，那此时它们之间距离是多少呢?设整个环的周长为C。此时它们之间的距离就变成了【C-1】
• 此时就需要在【C-1】的基础上再去考虑它们会不会相遇，那其实也是一样的道理，当【C-1】为偶数时，它们会相遇，当【C-1】为奇数时，它们之间的距离依旧会变回【C-1】，此时真的就变成一个环了，两个指针在里面绕来绕去就是不会相交，【fast】永远都追不上【slow】

• 那这个问题的其他示例其实也是一样，比如说快指针每次走5步、走6步，慢指针走个2步、3步，其实都是一个道理，只不过要进行一个取余运算，最后的结果还是一样，只要他们之间的距离为奇数，那么就永远追不上

---

【最后我们可以得出结论：当两个指针的相对速度为1时，一定能相遇；当两个指针的相对速度> 1时，则需要视两个指针之间的距离而定】

四、进阶:如何求出环的入口结点

• 此进阶为是环形链表|的后一道题
  声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/64510