面试热点题：环形链表及环形链表寻找环入口结点问题_力扣022 环形链表

141.环形链表

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

思路：

思路一：暴力解法
 我们从头遍历链表，每遍历一个节点，就再从头检查该节点是否已经出现过，如果直到遍历完也没出现则为false，反之为true。这是我们首先可以想到的暴力解法！时间复杂度O(N^2)空间复杂度O(1)。

思路二：快慢指针

 我们创建两个指针slow与fast,让他们同时指向头节点，slow每次走一步，fast每次走两步。fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。这是因为fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。

 如果循环最后的结果是 slow=fast 那么链表是环，如果 fast=nullptr 那么链表不是环。

 道理跟两个人一起跑步是一样的，跑道是环状的，且一直跑，那么快的那个人一定会在同一起跑线开始跑后再一次追上慢的人。

参考代码：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow=head;
        ListNode* fast=head;
        while(slow && fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            {
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

易错点：

剑指 Offer II 022. 链表中环的入口节点

问题：
给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
来源：力扣（LeetCode）

思路：

先证明链表有环，然后再找入口节点。假如有环，那么我们一定是slow走的距离是fast走的距离的二分之一，且看下图分析

由slow与fast的关系我们可以得出下面公式
slow的距离=Y＋X1
fast的距离= Y+(X1+X2)*n +X1
X1+X2是一圈的距离，我们不知道fast多走了多少圈就用n代替
 最终的等式：
 2*slow=fast
 2*(Y+X1) = Y+(X1+X2)*n+X1

2*(Y+X1) =Y+(X1+X2)*n+X1化简为:Y=(X1+X2)*n-X1

由最后一个等式Y=(X1+X2)*(n-1)+X2我们可以推理一下:

• 如果n为1的情况，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。当 n为1的时候，公式就化解为 x = z，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
• n如果大于1的情况，就是fast指针在环形转n圈之后才遇到 slow指针。
  其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

 这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
我们将slow指针重新指向头节点，然后之前的fast指针是指向的相遇点，slow与fast现在每次只走一步，那么它们最后的相交点就是入口点

参考代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow=head;
        ListNode* fast=head;
        while(slow && fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            {
                break;
            }
        }
        if(fast==nullptr || fast->next==nullptr)
        {
            return nullptr;
        }
        slow=head;
        while(slow!=fast)
        {
            slow=slow->next;
            fast=fast->next;
        }
        return fast;
    }
};
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

---

如有错误或者不清楚的地方欢迎私信或者评论指出

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/600040