the length of cycle: b + c
the distance that slow pointer moved: a + b
the distance that fast pointer moved: a + b + k(b + c)
The distance of the fast is twice that the slow:
2(a + b) = a + b + k(b + c)
=> 2a + 2b = a + b + b + c + (k - 1)(b+ c)
=> (a - c) = (k - 1)(b + c)
What does it mean?
When the slow comes to the entry, the distance between the head and the slow is (k - 1)(b + c)
Then, if those two pointers keep moving, they will meet each other at the entry.
python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast is slow:
while slow is not head:
slow = slow.next
head = head.next
return slow
return None