力扣142 - 环形链表||【二重双指针+哈希表】

一、原题描述

原题传送门
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

示例 1：

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

示例 2：

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

示例 3：

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

二、思路分析（重点）

本题的两个主要思考点是：
1.判断链表是否有环
2.如果有环，那如何找到这个环的入口

思考一：链表是否有环（双指针思路）

• 有做过这道题目的小伙伴应该都想到双指针这个思路，定义两个快慢指针，如果两个指针在移动过程中相遇了，说明此链表有环，如果快慢指针一直移动但是不相遇，则表明此链表一定没有环
• 因为我们就选择去定义一个快指针fast和一个慢指针slow，既然说是快慢指针，则表示它们移动的速度一定是不同的，我们让快指针每次移动两个结点，慢指针每次移动一个结点，这么定义其实就是为了实现让快指针在环中去追赶慢指针的一个动作，但是有些小伙伴就比较疑惑一个点？
  快慢指针一定会相遇吗？难道快指针在移动的过程中就不会错过慢指针吗？
• 答案是：是的，它们一定会相遇，因为快指针就比慢指针每次多走一格，它是在一个结点一个结点地去靠近慢指针。但如果快指针每次走的步数是三个结点，那就不一定了，可能会出现错位

先粗略地画一下，大概是这么个结构（比较丑凑合着看👺）

思考二：如果有环，怎么找到环的入口（数学思维）

• 假设此刻我们已经知道了这个链表一定是有环的，那么我们怎么去找到这个环形的入口结点呢，这就需要用到数学的思维了🎓
• 我们设头结点到环形入口结点的距离为x
• 入口结点到快慢指针相遇点的距离为y
• 然后从这个相遇点再回到环形点的入口为z
• 大致结构如下图所示👇
  
• 这里的需要根据快慢指针的每次的移动距离去确定一个等式，

慢指针：x + y 每次移动一步
快指针：x + y + n(y + z) 每次移动两步

2(x + y) = x + y + n(y + z)

• 消去一个x + y可以得到

x + y = n(y + z)

• 由题目意思可以知道，要我们求的是链表入环的第一个结点，因此就是我们设的这段x距离，所以我们把y移到右边

x = n(y + z) - y

• 但是这样子我们看不出x和什么正数有关系，因此想到让出一圈的距离，将n变为(n - 1)，然后配好后面的关系，可以得到如下关系式

x = (n - 1) (y + z) + z

• 从如上表达式我们就可以看出x和z是有着关系的，这里的n一定是>=1的，因为快指针不可以再第一圈的时候就和慢指针相遇，上面有提到快指针它是在追赶慢指针的一个过程，所以一定是在慢指针进入环内，然后快指针在饶了1圈或n圈后，才环内的某一个结点相遇的，这里当n = 1是，等式就变成了

x = z

• 这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是环形入口的节点
• 此处就是标题说到的第二重双指针了，设

index1 = fast
index2 = head

• 两个指针每次只移动一个结点，用一个while循环去控制，直到他们相遇返回任一index即可

三、动画展示（微信手机端看不到）

1、第一重双指针

2、第二重双指针

四、代码详解

这道题重点在于思路，知道你思路清楚了，代码是很好写的🔑

1、分步说明

• 首先定义两个快慢指针分别最初均指向头结点

 ListNode* fast = head;
 ListNode* slow = head;
1
2

• 接着就是通过一个外层的while循环判断快指针是否为空，因为快指针走在前面，但是为什么要判断next呢，因为快指针每次是走两步，因为不仅要判断当前所指结点是否为空，而且下一个结点也需要判断

while(fast != NULL && fast->next != NULL){
     slow = slow->next;          //慢指针每次移动一步
     fast = fast->next->next;        //快指针每次移动两步
1
2
3

• 然后就是去判断两个结点在环中是否相遇，若相遇就定义第二重指针去继续遍历

 if(fast == slow){       //当两指针在环中相遇时
     ListNode* index1 = fast;        //定义一个结点指向相遇的结点
     ListNode* index2 = head;        //定义一个结点指向头结点
1
2
3

• 内部也使用一个while循环去控制，直到两个index指针移动到环形入口时

 //继续遍历，直到两结点都运动到环形入口的起始位置
 while(index1 != index2){
     index1 = index1->next;
     index2 = index2->next;
 }
 return index1;
1
2
3
4
5
6

2、整体代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        //因为快指针需移动两步，因为要判断两个位置
        while(fast != NULL && fast->next != NULL){
            slow = slow->next;          //慢指针每次移动一步
            fast = fast->next->next;        //快指针每次移动两步
            if(fast == slow){       //当两指针在环中相遇时
                ListNode* index1 = fast;        //定义一个结点指向相遇的结点
                ListNode* index2 = head;        //定义一个结点指向头结点

                //继续遍历，直到两结点都运动到环形入口的起始位置
                while(index1 != index2){
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return NULL;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

五、疑难解答

1、n一定为1吗? 20圈? 50圈?

n 其实不一定为1，也可以转20圈，转50圈，最后在第二重双指针时，index1可能也会在圈中传转了一圈又一圈，index2才到达环形入口处，所以你n为50，为100都是一样的，这里设置为1，只是看得时候清晰方便一些，可以很快地得出x和z之间的关系，然后去写出代码逻辑

2、慢指针为什么一定在第一圈时和快指针相遇?

• 有些小伙伴可能对慢指针为什么只走了x + y步有所疑惑，为什么慢指针只在环了转的第一圈就和快指针相遇了呢，慢指针为什么不能转了x + y + k(y + z)圈呢❔

因为快指针一定是先进入环内的，然后慢指针才进到环内，然后当慢指针进入下一个入口时，快指针走的一定是慢指针的两倍，所以慢指针在没有进入到下一个入口处时，快指针在中间的某个位置一定和其相遇了

证明如下：

在快指针fast进入环口3时，它已经走了k + n个结点，从图中可以清晰地看出，k为快指针和慢指针之间的距离，n为一个环的距离，而慢指针在进入环内相应地走了(k + n)/2个结点，从图中可以看出k是小于n的，所以(k + n)/2也一样是小于n的，即慢指针在进入环内一圈不到的距离就会和快指针相遇

所以慢指针走动的距离为x + y就够了，其不会再走第二圈

原理图

六、其他方法

• 对于本题，还有一种解法就是哈希表，具体的思路就是哈希表的常用操作，如果您不太了解哈希表，我在一文带你快速入门【哈希表】对哈希表有做过详细讲解，可以先去了解一下
• 本题的思路就是只操作头结点指针，判断其是否为空，若其不为空，则取哈希表中查找是否遍历过此结点，若是遍历过，则返回此头结点所在位置；若是没有遍历过，则将此结点插入哈希表中为后续的遍历做铺垫
• 哈希表的解法还是很好理解的，本文重点需要掌握的是二重双指针的用法，主要是起到一个训练思维的效果，所以大家着重理解双指针的解法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> visited;
        while(head != NULL){
            if(visited.count(head))     //若在哈希表中发现有遍历过的结点
                return head;            //则返回此环的起始结点
            visited.insert(head);       //若在哈希表中没找到，则将其插入表中
            head = head->next;          //头结点继续向后移动
        }
        return NULL;            //若遍历到为空，则说明链表一定无环
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

七、回顾总结

看了本文，您对环形链表的理解有没有更加深入了呢，如果还觉得有些模糊，则应该配合动画和原理图的分析再去推理一遍，这题在力扣中虽然属于中等题，但是双指针的这种解法还是比较难理解的，主要还在于数学的推理分析过程🔍

OK，本次的讲解就到这里，感谢您对于本文的观看，如果疑惑请于评论区留言或私信给我🌹