# Solution

# HashSet

Use hashset to store mappings from ListNode to index.

Complexity

time: $O(n)$
space: $O(n)$

def detectCycle(self, head: ListNode) -> ListNode:
hashset = set()
while curr:
if curr in hashset:
return curr
else:
curr = curr.next
return None

1
2
3
4
5
6
7
8
9
10

Can you solve it using constant space?

# Floyd's Cycle-Finding Algorithm

When slow and fast intersect, fast has traversed the cycle once and completed twice the distance of slow. So:

\begin{aligned} 2 \cdot \text{distance(slow)} &= \text{distance(fast)} \\ 2(F+a) &= F+a+b+a \\ 2F+2a &= F+2a+b \\ F &= b \end{aligned}

Complexity

time: $O(n)$
space: $O(1)$

def detectCycle(self, head: ListNode) -> ListNode:
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: break
if slow is not fast: return None

# slow and fast intersect, cycle exists
# now finds the cycle start
ptr2 = slow
while ptr1 != ptr2:
ptr1 = ptr1.next
ptr2 = ptr2.next
return ptr1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18