《程序员面试金典（第6版）》面试题 02.08. 环路检测（哈希法，双指针，检测链表是否有环）网站首页 技术杂谈

《程序员面试金典（第6版）》面试题 02.08. 环路检测（哈希法，双指针，检测链表是否有环）

阿宋同学 2024-06-27 12:01:03

简介《程序员面试金典（第6版）》面试题 02.08. 环路检测（哈希法，双指针，检测链表是否有环）

题目描述

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。
题目传送门：面试题 02.08. 环路检测

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

示例 1：

在这里插入图片描述

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

示例 2：

在这里插入图片描述

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

示例 3：

在这里插入图片描述

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

进阶：

你是否可以不用额外空间解决此题？

解题思路与代码

这道题算是比较简单的一道题。检测链表是否存在环的最简单的一种方法是哈希法，其次就是快慢指针法。那么前者的空间复杂度可能会高些，但是代码结构简单易懂。
后者虽然说比前者稍微难点，但也没有难太多，多了一点点的思考量而已。

总的来说，这道题是一道好题，考验了你一点点的数学思维，与链表的实际操作

方案一：哈希法

这道题如果是单单的判断链表是否成环，那这道题就是一道简单题，如果还要让你去返回成环的开头节点，那这道题的难度就要上升了。

对于这道题，如果我们用了哈希法，那就是降维打击，因为我们利用unordered_set就可以直接帮你返回相同节点。
具体的代码如下：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> set;
        while(head){
            if(set.count(head)) return head;
            set.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};

在这里插入图片描述

复杂度分析：

时间复杂度：O(n),其中n是链表节点的个数
空间复杂度：O(n),我们需要将链表的每一个节点放入集合中，所以是O(n)

方案二：快慢指针法

先解释一下这里的快慢指针法是什么意思。在这里，我们先设置两个指针，p1，p2。 p1一次走一格，p2一次走两个。因为他们走的步数不一样，所以，如果链表中有环存在了话，那么p1，p2一定不会相等。反之，如果有环，那p1，p2一定会相等。

那这道题的难点在成环节点，在距离头节点多少位置呢？首先，我们要画图分析。
在这里插入图片描述

我们设从头节点，到成环节点的距离为a，成环节点到p2追到p1的距离为b，被追到的p1节点距离再次回到成环节点的距离为c。
p2指针一次走两格，p1指针一次走一格，p2追上p1的时候，p2走过的距离是p1的两倍。
p1被追到时p2走了a + n(b + c) + b，p1走了a + b所以不难得出这个等式：a + n(b + c) + b = 2(a + b)
将这个等式变化一下便是 **a = c + (n-1)(b+c)**么。

看着这个图，我们来翻译一个这个数学等式的意思。

假设从头节点走了a步，到达了成环节点。便等于我在相遇节点走了 c 步 + n圈。
我们在p1节点与p2节点相遇的时候，再去设置一个p3节点让它等于头节点。这个时候，p3也一次走一步。
你看图，当p3在头节点走了a步的时候，是不是正好与p1在b的时候走了c步 + n圈呢？

具体代码如下：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* p1 = head;
        ListNode* p2 = head;
        while(p2){
            p1 = p1->next;
            if(p2->next)
                p2 = p2->next->next;
            else return nullptr;
            if(p1 == p2) {
                ListNode* p3 = head;
                while(p3!=p1){
                    p1 = p1->next;
                    p3 = p3->next;
                }
                return p3;
            }
        }
        return nullptr;
    }
};