https://leetcode.cn/problems/linked-list-cycle-ii/
需要注意的点
1. 环头节点(环头),链表的头节点(链头),fast 跟slow 相遇的节点(相遇点)
走n圈,环头到链头为a,slow 到相遇点为b, fast 在环里面走c,
环的长度是b+c
fast走过的距离是
fast = a + n(b+c)+b = a + (n+1)b+nc
slow走过的距离是
slow = a+b
等式
a + (n+1)b+nc = 2(a+b)
== a = c + (n-1)(b+c)
# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution:def detectCycle(self, head: ListNode) -> ListNode:'''环头节点(环头),链表的头节点(链头),fast 跟slow 相遇的节点(相遇点)走n圈,环头到链头为a,slow 到相遇点为b, fast 在环里面走c,环的长度是b+cfast走过的距离是fast = a + n(b+c)+b = a + (n+1)b+ncslow走过的距离是slow = a+b等式a + (n+1)b+nc = 2(a+b)== a = c + (n-1)(b+c)'''slow = headfast = headwhile fast and fast.next:fast = fast.next.nextslow = slow.nextif fast == slow:a = fastb = headwhile a != b:a = a.nextb = b.nextreturn areturn None
