难度: Medium
给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
示例 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 解释：链表中没有环。
进阶：
运行时间: 60 ms
内存: 17.9 MB
# 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:
if head is None or head.next is None:
return None
f = s = head
while f and f.next:
f = f.next.next
s = s.next
if f == s:
break
if f is None or f.next is None:
return None
f = head
while f != s:
f = f.next
s = s.next
return f
这个题解使用了快慢指针的方法来检测链表中是否存在环，并找到环的入口。首先，设置两个指针s（慢指针）和f（快指针），它们都从头节点开始。慢指针每次移动一步，快指针每次移动两步。如果链表中存在环，那么快慢指针最终会在环内相遇。在快慢指针相遇后，将快指针重新指向头节点，然后快慢指针都每次移动一步，直到它们再次相遇的位置，这个位置就是环的入口。
时间复杂度: O(n)
空间复杂度: O(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:
if head is None or head.next is None:
return None # 如果链表为空或只有一个节点，返回None
f = s = head # 初始化快慢指针
while f and f.next:
f = f.next.next # 快指针每次移动两步
s = s.next # 慢指针每次移动一步
if f == s:
break # 如果快慢指针相遇，表明存在环
if f is None or f.next is None:
return None # 如果快指针遇到null，说明链表无环
f = head # 将快指针重置到链表头部
while f != s:
f = f.next # 快慢指针均每步前进一步
s = s.next
return f # 当快慢指针再次相遇时，位置即为环的起点
当快慢指针在环中首次相遇时，可以推断出快指针比慢指针多走了环的长度的整数倍。假设从头节点到环入口的距离为D，环的周长为C，并且当快慢指针首次相遇时慢指针已经在环中走了K步（K可能小于C）。在首次相遇点，快指针走的步数为D + nC + K（n为快指针绕环的圈数），且快指针走的步数是慢指针的两倍，即2(D + K)。通过这些等式，我们可以推导出D = (n-1)C + (C-K)。这意味着从链表头到环入口的距离等于从相遇点绕环走回到入口的距离。因此，当你将快指针重置到头节点后，它们以相同的速度移动，最终会在环的入口相遇。
不会。快指针每次移动两步并不会导致跳过环的入口。无论链表有多长或环的大小如何，快指针移动的步数始终是连续的，并且每次只跳过一个节点。因此，即使链表非常大或环很小，快指针也不可能跳过环的入口。
这是基于数学推导得出的结论。首次相遇后，我们知道从链表头到环入口的距离与从相遇点绕环回到入口的距离相等。因此，当我们将一个指针重置到链表头部，另一个指针保留在首次相遇点，然后让它们以相同的速度移动时，它们会在环入口相遇。这是因为它们同时开始向环入口移动，并且以相同的速度行进，所以它们必须同时到达环入口。
是的，这个算法仍然适用，无论环的大小。算法的核心在于快慢指针的相遇点和数学推导，说明从链表头到环入口的距离等于从相遇点绕环到达入口的距离。因此，无论环有多大或多小，只要存在环，该算法都能正确地找到环的入口。