# \[142]\[中等]\[双指针] 环形链表 II

## 题目描述

[142. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/)

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

```
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
```

![](/files/-MI7NrrdOiwHwlGuzMIV)

示例 2：

```
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
```

![](/files/-MI7Ns0dH9WiLe8dclyn)

示例 3：

```
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
```

![](/files/-MI7Ns1FQMk41WOwN1hr)

进阶：

* 你是否可以不用额外空间解决此题？

## 解题思路

依旧是快慢指针.

![](/files/-MI7NrriRQ13OKU4VEum)

如果有环, 假设在快慢指针相遇时, 慢指针走了$$k$$步, 快指针走了$$2k$$步. 设相遇点距环的起点的距离为$$m$$, 那么环的起点距离头结点的距离为$$k-m$$, 而且快指针已经走完了一圈环, 抛开覆盖的慢指针走过的路, 以及覆盖的两者都走过的环起点到相遇点的路长$$m$$, 则相遇点到环起点的距离也为$$k-m$$.

因此在相遇后, 将其中一个指针重新放置在头节点处, 两个指针再次相遇时, 就是在环起点的位置, 计数走的步数, 就是最终的结果.

![](/files/-MI7Nrrlqcxwf3FeRTcj)

![](/files/-MI7NrrpE7d6WGX5doHA)

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                slow = head
                while slow is not fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/shuang-zhi-zhen/142-huan-xing-lian-biao-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.