The Blind 75 Leetcode Series: Linked List Cycle

Photo by Chris Ried on Unsplash

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).