《程序员面试金典（第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;}
};

复杂度分析：

• 时间复杂度：O(N),N为节点的长度。因为你在实际推演的过程中会发现，p1指针走过的最长的路程也不会超过链表中节点的个数，而是等于节点的个数，所以时间复杂度是O(N)
• 空间复杂度：O(1),我们设置了几个变量而已，没有使用额外的数据结构，所以是O(1)。

总结

这道题目是一个经典的链表问题，经常出现在计算机科学和软件工程的面试和教程中。

这道题目的主要意义和重要性可以从以下几个方面来看：

• 数据结构理解与应用：这道题目需要你理解和操作链表这种基础数据结构。理解数据结构的特性和操作方法是编程和算法学习的基础。

• 双指针技巧：这道题目需要使用到双指针（快慢指针）的技巧。这是一个常用的算法设计策略，可以帮助解决一些看似复杂的问题。

• 算法分析：通过这道题目，你需要理解和分析算法的时间复杂度和空间复杂度。这道题的解决方案有一个很好的性质：它只需要常量的额外空间，且时间复杂度为线性。

• 问题解决和调试能力：这道题目也可以帮助你提升问题解决和调试的能力。理解为什么这个解决方案能够工作，对于提升你的算法设计和问题解决能力是非常有帮助的。

所以，这道题目的意义不仅仅是解决一个具体的问题，更重要的是通过这个问题来学习和提升你的数据结构知识，算法设计和问题解决能力。

最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。