题目
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
- 你是否可以使用
O(1)空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
- 链表中节点的数目范围在范围
[0, 10^4]内 -10^5 <= Node.val <= 10^5pos的值为-1或者链表中的一个有效索引
题解
这题使用经典的快慢指针来做：
- 两个指针都是从表头开始出发
- 慢指针一次移动1步
- 快指针一次移动2步
- 如果有环，快指针一定会再次追上慢指针，因此两者必然在环内相遇
首先设入环之前的长度为 a，环的长度为 m，假定快慢指针的相遇处离入环点的距离为 b 。
假设此时慢指针已经在环内走了n圈，那么：
- 慢指针一共走过的距离为
- 快指针一共走过的距离为
可列出等式关系：
简化可得：
也就是说，在相遇处，再走 a步就能回到入环点。
那么问题就来了， a 等于多少呢？
答案是不知道，但我们也不需要知道。
我们可以再次使用双指针，一个从表头出发，另一个从b出发，走a步之后，它们俩必然在入环点相遇。
于是，最终我们就得到了入环点的位置。
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
i = head
j = head
if j == None:
return None
flag = 0
while j.next and j.next.next:
i = i.next
j = j.next.next
if i == j:
flag = 1
break
if flag == 0:
return None
i = head
while i != j:
i = i.next
j = j.next
return i
若有收获，就点个赞吧
0 人点赞
