> For the complete documentation index, see [llms.txt](https://suki.gitbook.io/91-days-algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/11.linked-list-cycle-ii.md).
# 142.环形链表 II
* [142.环形链表 II](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#142环形链表-ii)
* [题目描述](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#题目描述)
* [方法 1：哈希法](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#方法-1哈希法)
* [思路](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#思路)
* [复杂度分析](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#复杂度分析)
* [代码(JavaScript/C++)](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#代码javascriptc)
* [方法 2：双指针](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#方法-2双指针)
* [思路](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#思路-1)
* [复杂度分析](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#复杂度分析-1)
* [代码(JavaScript)](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#代码javascript)
* [方法 3：双指针 + 数学证明](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#方法-3双指针--数学证明)
* [思路](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#思路-2)
* [复杂度分析](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#复杂度分析-2)
* [代码(JavaScript/C++)](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDonExVf32-q2Nlq_#代码javascriptc-1)
## 题目描述
```
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
进阶：
你是否可以不用额外空间解决此题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```
## 方法 1：哈希法
### 思路
1. 可以从头开始遍历链表并给每个节点增加一个“已遍历”的标记；
2. 如果在遍历过程中遇到了一个“已遍历”的节点，说明这就是环的入口；
3. 但题目不允许修改给定的链表，所以我们可以用一个额外的 hashmap 来记录；
4. 注意题目中没有提到节点值是否唯一，所以仅用节点值作为 hashmap 的 key 是不够的，需要用到整个节点对象来当 key。
### 复杂度分析
* 时间复杂度：$O(n)$, n 为链表长度。
* 空间复杂度：$O(n)$。
### 代码(JavaScript/C++)
JavaScript Code
```javascript
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function (head) {
const map = new Map();
while (head) {
if (map.has(head)) return head;
map.set(head, true);
head = head.next;
}
return null;
};
```
C++ Code
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
set seen;
ListNode *cur = head;
while (cur != NULL) {
if (seen.find(cur) != seen.end()) return cur;
seen.insert(cur);
cur = cur->next;
}
return NULL;
}
};
```
## 方法 2：双指针
### 思路
1. 先使用快慢指针确定链表是否有环；
2. 如果链表有环，那快慢指针相遇的点一定是在环中；
3. 接着把指针 A 移到链表头部，指针 B 留在环内；
4. 指针 A 开始遍历环外的节点，指针 B 遍历环内的节点，指针 A 每走一步，指针 B 在环内走一圈；
5. 如果指针 A 和指针 B 相遇了，说明这个节点就是环的入口。
> 因为环和环外的唯一交点就是环的入口点
### 复杂度分析
* 时间复杂度：$O(n\*p)$, n 是环外链表的长度，p 是环的长度。
* 空间复杂度：$O(1)$。
### 代码(JavaScript)
JavaScript Code
```javascript
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function (head) {
let slow = head,
fast = head;
// 快慢指针确定有环
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
// 确定有环，开始找环的第一个节点
if (slow === fast) return findConnection(head, fast);
}
return null;
// ******************************************
function findConnection(head, loopNode) {
// p1 走一步，p2 绕环一圈
let p1 = head;
while (true) {
let p2 = loopNode;
while (p2.next !== loopNode && p2.next !== p1) {
p2 = p2.next;
}
if (p2.next === p1) return p1;
p1 = p1.next;
}
}
};
```
Python Code
```python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow = fast = head
while slow != None and fast != None and fast.next != None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return self.findConnection(head, slow)
return None
def findConnection(self, head, loopNode):
p1 = head
while True:
p2 = loopNode
while p2.next != loopNode and p2.next != p1:
p2 = p2.next
if p2.next == p1:
return p1
p1 = p1.next
```
## 方法 3：双指针 + 数学证明
### 思路
先用快慢指针确定链表是否有环，如果是环形链表，快慢指针会在环内的某个节点相遇。
我们分别来看一下两个指针相遇前分别走了多少路程。
**快指针**
假设走到相遇点之前，快指针在环内走了 x 圈，那快指针走过的总路程可以用
`S(fast) = a + x(b + c) + b`
来表示，其中 `(b + c)` 就是环的长度。
**慢指针**
假设走到相遇点之前，慢指针在环内走了 y 圈，同理可得慢指针走过的总路程是
`S(slow) = a + y(b + c) + b`
而由于快指针的速度是慢指针速度的 2 倍，所以可得以下方程式：
`2S(slow) = S(fast)` => `2(a + x(b + c) + b) = a + y(b + c) + b`
稍微整理一下我们就得到了：
`a + b = (b + c)(x - 2y)`
如果我们把其中一个指针移动到链表头部，然后让两个指针以相同的速度移动。
它们会在环的入口相遇。
### 复杂度分析
* 时间复杂度：$O(n)$，n 为链表长度。
* 空间复杂度：$O(1)$。
### 代码(JavaScript/C++)
JavaScript Code
```javascript
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function (head) {
let fast = head,
slow = head;
// 快慢指针确定有环
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
// 确定有环，开始找环的第一个节点
if (fast === slow) {
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
};
```
C++ Code
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head;
ListNode *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
fast = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return NULL;
}
};
```
更多题解可以访问：