## # Solution

### # HashSet

Use the hashset to see if curr has been visited before.

Complexity

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

def hasCycle(self, head: ListNode) -> bool:
hashset = set()
while curr:
if curr in hashset:
return True
else:
curr = curr.next
return False

1
2
3
4
5
6
7
8
9
10

Can you solve it using constant space?

### # Floyd's Cycle-Finding Algorithm

Use two pointers, slow and fast, to traverse the linked list and see if they eventually meet.

Complexity

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

#### # Check False

If statement is at beginning of while loop.

def hasCycle(self, head: ListNode) -> bool:
while slow is not fast:
if not fast or not fast.next: return False
slow = slow.next
fast = fast.next.next
return True

1
2
3
4
5
6
7
8
9

#### # Check True

def hasCycle(self, head: ListNode) -> bool:
return False
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False

1
2
3
4
5
6
7
8
9
10

#### # Try / Except

When fast or fast.next is None, an error would throw on the while check. To avoid the check, return True at the end of try and False at the end of except.

def hasCycle(self, head: ListNode) -> bool:
try:
while slow is not fast:
slow = slow.next
fast = fast.next.next
return True
except:
return False

1
2
3
4
5
6
7
8
9
10