142. 环形链表 II
题目链接：142. 环形链表 II(中等)
题目描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：你是否可以使用 O(1) 空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
-
链表中节点的数目范围在范围 [0, 104] 内
-
-105 <= Node.val <= 105
-
pos 的值为 -1 或者链表中的一个有效索引
题解
思路1：哈希表法
使用哈希表遍历链表中的每个节点并记录下来；如果遇到已经遍历过的节点，则说明链表中存在环，并且当前节点就是环的入口节点
代码(C++)
//哈希法
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode*> visited;
while (head != NULL) {
//如果head所指的节点的指针已经存储在链表中了，则count一定会为 1 ，进入循环
if (visited.count(head)) {
return head;
}
//如果所指节点的指针不存在，则存入集合中
visited.insert(head);
head = head->next;
}
return NULL;
}
分析：
-
时间复杂度：O(N)
-
空间复杂度：O(N)
思路2：快慢指针法
使用快指针 fp 和慢指针 sp ，一开始他们都指向head所指的节点。之后，快指针以每次移动两个节点的速度移动，慢指针以每次移动一个节点的速度移动。如果链表当中存在环，则快慢指针一定会在环中相遇。下一步就是要找入环节点。
如上图所示，设链表中环外部分的长度为 a。sp 指针进入环后，又走了 b 的距离与 fp 相遇。此时，fp 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。
根据题意，任意时刻，fp 指针走过的距离都为 sp 指针的 2 倍。因此，我们有 a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
有了 a=c+(n−1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。
因此，当发现 sp 与 fp 相遇时，我们再额外使用一个指针 tp。起始，它指向链表头部；随后，它和 sp 每次向后移动一个位置。最终，它们会在入环点相遇。
代码(C++)
//快慢指针法
ListNode *detectCycle(ListNode *head) {
ListNode* sp = head;
ListNode* fp = head;
while (fp != NULL && fp->next != NULL) {
fp = fp->next->next;
sp = sp->next;
//判断是否相遇
if (sp == fp) {
ListNode* tp = head;
//找如环节点
while (tp != sp) {
sp = sp->next;
tp = tp->next;
}
return tp;
}
}
return NULL;
}
分析：
-
时间复杂度：O(N)
-
空间复杂度：O(1)
参考链接