一、题目描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
进阶：
你是否可以不用额外空间解决此题？
二、思路
1. 快慢指针leetcode官网题解
使用两个指针，p1和p2。它们都起始于链表头部，当p1指针每次向后移动一个位置，p2指针则向后移动两个位置。如果链表中存在环，那么p1、p2肯定会在环中相遇。
如下图所示，假设链表中存在环，且环外部分的链表长度为a，b+c为整个环的长度。假设p1指针在环内走了距离b，然后与p2指针相遇，这时p2指针已经在环内走了n圈因此可以得出p2走过的距离公式：a + n(b+c) + b。
因为p2指针每次走的距离都是p1指针走过距离的2倍，所以p2走过的总距离也是p1的2倍。因此：a + n(b+c) + b = 2(a+b) ==> a = (n-1)b + nc。
上边的等式又可以变化成a = (n-1)(b+c) + c，从这个等式我们可以发现，从相遇点到入环点的距离再加上n-1圈的环长，正好等于链表从头部到入环点的距离a。
所有在指针p1和p2相遇的的时候，我们可以创建一个新的指针p3，并将其指向链表的头。然后让p3和p1同时向后每次移动一个位置，最后，它们将会在入环点相遇。
三、代码实现
1. 快慢指针
# 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:
p1 = head
p2 = head
while p2 and p2.next:
p1 = p1.next
p2 = p2.next.next
if p1 == p2:
p3 = head
while p3 != p1:
p3 = p3.next
p1 = p1.next
return p1
return
四、表现
| method | 运行时间 | 表现 | 内存消耗 | 表现 |
|---|---|---|---|---|
| 1. 快慢指针 | 56ms | 94.70% | 16.1MB | 95.81% |
