# The Blind 75 Leetcode Series: Linked List Cycle

Today, we are working on 141. Linked List Cycle

Given `head`, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that tail's `next` pointer is connected to. Note that `pos` is not passed as a parameter.

Return `true` if there is a cycle in the linked list. Otherwise, return `false`.

We have a linked list that might be circular, meaning the `next` node of the last node is pointing to a previously visited node in the linked list. We want to see if this given list is actually circular.

We might wanna check if

1. we are expecting empty list
2. we are expecting double circular list (if there are 2 circles in this list)

If the interviewer tells us that we are expecting empty list and we are only expecting 1 circle, then we can continue.

This list can be circular or not circular. We know it’s not circular if we reach the end (i.e. we see an NoneType), but we don’t know when that’ll happen and IF that would happen. In a circular list, we would never reach the end.

So we want to have another condition. We know that if a list is circular, we would eventually hit the same node. Therefore, if we can track the existence of each node, then we know the list is circular if we’ve seen the same node.

We can do something like this

`def hasCycle(head):    if not head or not head.next:        return False    tracker = set([head])    while head.next:        head = head.next        if head in tracker:            return True        tracker.add(head)    return False`

What’s the time complexity? If it’s circular, we need to go through the entire list once before we can possibly find the repeating node, so it’s linear to length of list, therefore O(n).