> 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
解释：链表中有一个环，其尾部连接到第二个节点。
```

![](https://3713032588-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LUx2ALWjDXrP_paswc_%2Fsync%2Fb0111ae63637e77ab1a7ac7f2321a55083dbbb80.png?generation=1598543459778696\&alt=media)

示例 2：

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

![](https://3713032588-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LUx2ALWjDXrP_paswc_%2Fsync%2F634e7a47f5d938e455e51260147a96e02888f5d9.png?generation=1598543460390270\&alt=media)

示例 3：

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

![](https://3713032588-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LUx2ALWjDXrP_paswc_%2Fsync%2F9f11a9e45492351b226f682770b61ac259f4efc3.png?generation=1598543459952822\&alt=media)

进阶：

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

## 解题思路

依旧是快慢指针.

![](https://3713032588-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LUx2ALWjDXrP_paswc_%2Fsync%2Fc1fe49a23797f2632582ced9f3940abb6556b4c1.png?generation=1598543460854372\&alt=media)

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

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

![](https://3713032588-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LUx2ALWjDXrP_paswc_%2Fsync%2F7d7bd77193ff8a732f7ce545e4451213949dc36c.png?generation=1598543460671838\&alt=media)

![](https://3713032588-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LUx2ALWjDXrP_paswc_%2Fsync%2Fde27d35383e1b3a3557ca3015508210cf8c1adee.png?generation=1598543460285820\&alt=media)

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