链表：判断链表是否有环以及找入口_判断链表环的入口

141环形链表

---

题意： 给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

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

说明：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

思路：

这道题目，主要考察对链表的操作。

主要方法：
■ 双指针：快慢指针

---

双指针：快慢指针

变量：首先定义 fast 和 slow 快慢指针。

操作：从头结点出发，fast指针每次移动两个结点，slow指针每次移动一个结点。如果fast和slow指针在途中相遇，说明这个链表有环返回true。如果fast最后走到了空结点，说明这个链表没有环返回false。

为什么fast一次走两个结点，slow一次走一个结点，如果有环的话，一定会在环内相遇呢，而不会永远的错开？

首先明确一点：如果有环，fast指针一定是先入环，slow指针后入环，如果要相遇那么一定会在环内相遇。fast指针一定会在slow指针的前面。

其次：为什么fast指针和slow指针一定会相遇呢？

我们知道 fast 指针一次移动两个结点，slow指针一次移动一个结点。fast 指针相对于 slow 指针每次移动一个结点，然后又是在环内，fast 又在 slow 的 前 面，就相当于fast在slow后面追赶slow,每次向slow靠近一步。所以最后一定就会把slow指针追上。

最终情况，如下图：

---

---

思考问题：

slow指针在环内走过的结点会不会超过一圈？

请看极限情况，fast和slow的相差距离为C-1。如下图。

---

---

设环的长度为 C 时，考虑极限最大情况下fast和slow指针相差C-1个结点。当在slow指针进入环后，设fast指针走了Y的长度，slow指针走了X的长度，所以有等式 Y-X=C-1, Y=2*X, ==> X = C-1。所以在极限情况下慢指针进入环内最多在环中走了C-1个结点，所以不会超过一圈。

---

fast 指针在环内走过的结点最少是多少呢？

请看极限情况，fast和slow的相差距离为0时。如下图。

---

---

设环的长度为 C 时，考虑极限最小情况下fast和slow指针相差0个结点，即慢指针刚刚进入环就遇见快指针。当在slow指针进入环后，设fast指针走了Y的长度，slow指针走了X的长度，所以有等式 Y-X=0, Y=2*X, ==> Y= 0。但是之前快指针最少已经走了C个节点，因此快指针进入环后相遇慢指针最少走了C个节点。

---

fast 指针为什么要一次走两个节点，一次走三步节点，一次走四个节点，最终还会不会和slow指针相遇呢？

答案是：可能会相遇，当快指针走三步时，快指针就相对于慢指针走2步，当最后慢指针和快指针刚刚相差一个节点时，这时快指针就刚刚跨过慢指针，所以这次就不会相遇了。走四步也是一样的。所以当快指针走两步时，就一定会相遇，因为快指针只相对于慢指针走一步，每次靠近一步，所以最后一定会相遇慢指针。

---

C++代码

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr||head->next==nullptr)return false;
        ListNode *fast=head;
        ListNode *slow=head;
        while(fast->next&&fast->next->next){
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast){ //一定要在移动了再判断。找到了直接返回true
                return true;
            }
        }
        return false; //说明没有环 fast走到了链表最后的空指针
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

142. 环形链表 II

题意： 给定一个链表，返回链表开始入环的第一个结点。如果链表无环，则返回null。为了表示给定链表中的环，使用整数pos来表示链表尾连接到链表中的位置(索引从0开始)。如果 pos 是 -1，则在链表中没有环

返回值：如果链表中存在环，则入环的第一个结点 。 否则，返回 null 。

说明： 不允许修改给定的链表。

思路：

1.这道题目，主要考察对链表的操作。2.还有数学的相关运算

主要方法：
■ 双指针：快慢指针，判断链表是否有环
■ 找到环之后怎么样找第一个入口，以及怎么证明。

---

双指针：快慢指针，判断是否有环

对于这个我在上面已经给出了相应的解释和方法了，相信大家都能看懂。

找到环之后怎么样找第一个入口，以及怎么证明。

当我们能够判断链表有环时，这下我们的目的就是怎样找到环的入口结点了。

---

变量：假设头节点到环的第一个入口节点的节点数为X。环形入口结点到fast指针和slow指针相遇节点 节点数为Y。环的节点数为C。那么相遇节点到环第一个入口节点的节点数为 C-Y。

证明：
■相遇时慢指针走过的节点数为X+Y：我在上面已经给出了证明慢指针在环内走过的节点数不会超过一圈。所以慢指针在环中走过的长度就是Y.
■相遇时快指针走过的节点数为X+NC+Y(N>=1)：我们不知道环的大小，当环很小时，快指针可能在环内已经走了很多圈了。
■相遇时有等式 X+NC+Y = 2(X+Y)：因为快指针是慢指针速度的两倍。解得等式有 X = NC-Y==>X = (N-1)C+C-Y。
■最后推出来的等式说明：从头节点出发一个指针，从相遇节点出发一个指针，这两个指针每次走一步，那么当这两个指针相遇时就是环形入口的节点。因为当N=1时，等式刚刚是X = C-Y，所以刚好相遇时就是环形入口节点。当N>1时，也能找到相遇节点，如果N>1就是一个指针在环内多绕 N-1 圈最后还是找到了环形的入口节点。

C++代码

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast=head;
        ListNode *slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast){	//相遇说明有环
                while(head!=slow){	
                    slow=slow->next;
                    head=head->next;
                }
                return head;
            }
        }
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19