# Linked List Cycle

`pos`

variable is used to:

- convert input array into linked list
- run unit test faster

The next problem is Linked List Cycle II, which asks for the cycle start.

## # Solution

### # HashSet

Use the HashSet `st`

to see if `curr`

has been visited before.

Complexity:

- time:
- space:

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

## # Follow Up

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:
- space:

#### # `slow is not fast`

If statement is at **beginning** of while loop.

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

#### # `fast and fast.next`

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

#### # Try / Except

When `fast`

or `fast.next`

is `None`

, an error would throw on the while check. To avoid the hassle, return `True`

at the end of `try`

and `False`

at the end of `except`

.

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