Today, we are working on 141. Linked List Cycle
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
posis used to denote the index of the node that tail's
nextpointer is connected to. Note that
posis not passed as a parameter.
trueif there is a cycle in the linked list. Otherwise, return
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
- we are expecting empty list
- 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
if not head or not head.next:
tracker = set([head])
head = head.next
if head in tracker:
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).