题目描述
- 如果链表中有某个节点，可以通过连续跟踪 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)。
总结
这道题目的主要意义和重要性可以从以下几个方面来看：
-
数据结构理解与应用：这道题目需要你理解和操作链表这种基础数据结构。理解数据结构的特性和操作方法是编程和算法学习的基础。
-
双指针技巧：这道题目需要使用到双指针（快慢指针）的技巧。这是一个常用的算法设计策略，可以帮助解决一些看似复杂的问题。
-
算法分析：通过这道题目，你需要理解和分析算法的时间复杂度和空间复杂度。这道题的解决方案有一个很好的性质：它只需要常量的额外空间，且时间复杂度为线性。
-
问题解决和调试能力：这道题目也可以帮助你提升问题解决和调试的能力。理解为什么这个解决方案能够工作，对于提升你的算法设计和问题解决能力是非常有帮助的。
所以，这道题目的意义不仅仅是解决一个具体的问题，更重要的是通过这个问题来学习和提升你的数据结构知识，算法设计和问题解决能力。
最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。