> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/suan-fa/shuang-zhi-zhen/142-huan-xing-lian-biao-ii.md).

# \[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/-MFkbJnQXwQJYj762ybD)

示例 2：

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

![](/files/-MFkbJnRQgxa4tYDUmmp)

示例 3：

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

![](/files/-MFkbJnSSrt7o_TL6PUd)

进阶：

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

## 解题思路

依旧是快慢指针.

![](/files/-MFkbJnTyMx3AtbPaCTX)

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

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

![](/files/-MFkbJnUD76w3534aGaO)

![](/files/-MFkbJnVSn-ABW3--vGh)

```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
```