题目描述
给定一个链表，如果它是有环链表，实现一个算法返回环路的
开头节点
。若环不存在，请返回
null
。
如果链表中有某个节点，可以通过连续跟踪
next
指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数
pos
来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果
pos
是
-1
，则在该链表中没有环。
注意：
pos
不作为参数进行传递
，仅仅是为了标识链表的实际情况。
解题思路1
首先考虑的就是
哈希表
的方式，使用指针遍历整个链表，遍历过后存入哈希表中，每次都检查该结点在哈希表中是否存在。若存在，则链表一定有环，且第一个重复结点就是入环结点；否则无环。
以下为c++ code：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
// 和 环形链表II 是一个题
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// 双指针 判断是否存在回路
ListNode* slow = head;
ListNode* fast = head;
while(fast != nullptr && fast->next != nullptr){
slow = slow->next;
fast = fast->next->next;
// 存在环的情况
if(slow == fast){
// // 找到入环点 - 这里初始有问题
// 你这都存在环了啊宝贝，那slow必定不会等于nullptr
// while(slow != nullptr){
// head = head->next;
// slow = slow->next;
// }
// return head;
ListNode* ptr = head;
while(ptr != slow){
ptr = ptr->next;
slow = slow->next;
}
return ptr;
}
}
// 否则不存在环
return nullptr;
}
};时间复杂度：O(N)，其中 N 为链表总结点个数。
空间复杂度：O(N)，因为使用了哈希表。
解题思路2
双指针解法，总体分两部：
I. 判断链表是否有环，若无环，则返回；否则确定有环。
II. 确定入环点。通过数学推导，又因为 slow 指针每次走一步，fast 每次走两步，二者步数始终为 1:2 关系。则可以通过 head 指针和 slow 指针找到入环点。
以下为 c++ code：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
// 和 环形链表II 是一个题
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// 双指针 判断是否存在回路
ListNode* slow = head;
ListNode* fast = head;
while(fast != nullptr && fast->next != nullptr){
slow = slow->next;
fast = fast->next->next;
// 存在环的情况
if(slow == fast){
// 确定入环点 - 这里需要依据数学推导式
ListNode* ptr = head;
while(ptr != slow){
ptr = ptr->next;
slow = slow->next;
}
return ptr;
}
}
// 否则不存在环
return nullptr;
}
};时间复杂度：O(N)，遍历链表有限遍。
空间复杂度：O(1)，只使用了有限个变量。