Reference: LeetCode EPI 7.3
Difficulty: Medium
My Post: Potential Methods & Analysis (When you understand the process, coding is super easy)
Problem
Given a linked list, return the node where the cycle begins. If there is no cycle, return
null
.
To represent a cycle in the given linked list, we use an integer
pos
which represents the position (0-indexed) in the linked list where tail connects to. Ifpos
is-1
, then there is no cycle in the linked list.
Example:
1 | Input: head = [3,2,0,-4], pos = 1 |
Note: Do not modify the linked list.
Follow up: Cau you solve it without using extra space? $O(1)$
Analysis
Hash Set
Time: $O(N)$
Space: $O(N)$ ❌
Mark Node
It modifies the linked list. ❌
Time: $O(N)$
Space: $O(1)$
Two Pointers
Reference: link
Why could slow and fast meet? See my analysis in 141. Linked List Cycle
Notations:
head
: the head node of the list.entry
: the entry node of the cycle.meeting
: the intersected node at whichslow
andfast
meet.L1
: the distance betweenhead
andentry
.L2
: the distance betweenentry
andmeeting
.C
: the length of the cycle.n
: how many timesfast
loops in the cycle.
Floyd’s Cycle Detection:
The first half is the same as in the two-pointer solution in Problem I
. To find the entry point, we can start traversing from head
and slow
at the meeting point in tandem. The node they meet is the entry node.
Why is the node they meet the entry node?
When slow
and fast
meet,
slow
movesL1 + L2
. (head
->meeting
)fast
movesL1 + L2 + n * C
.
Since each time fast
moves twice the step as slow
does, when they meet at meeting
node:
- We have:
2 * Dis(slow) = 2 * (L1 + L2) = L1 + L2 + n * C = Dis(fast)
=>L1 + L2 = n * C
. - Equivalent to:
L1 = (n - 1) * C + (C - L2)
whereC - L2
is the distance betweenmeeting
andentry
. - The equation indicates that if
slow
orfast
now starts moving frommeeting
and a new node starts moving fromhead
, they will finally meet at the entry node!- Consider a very big
L1
and a relatively shortC
. - Note that
(n - 1) * C
means thatslow
orfast
moves frommeeting
byn - 1
cycles and still stops atmeeting
.
- Consider a very big
Note:
- It’d better to start
slow
andfast
from the head both. - Move first! Otherwise, they must meet at the beginning.
1 | public ListNode useTwoPointers(ListNode head) { |
Time: $O(L1 + L2 + L1) < O(N + N + N) = O(3N) = O(N)$
- Distance that
slow
moves before they meet: $O(L1 + L2)$ - Distance that the
new node
moves afterslow
andfast
meet: $O(L1)$
Space: $O(1)$