The Blind 75 Leetcode Series: Linked List Cycle
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).
One problem, though, is that we don’t know how long this list is. Normally we don’t care about space complexity, but in this case, we CAN run out of memory.
Is there a a way we can do it without having a tracker?
Have you heard of the story of the tortoise and the hare? We have a race between a hare and a tortoise. Hare runs faster than tortoise, but hare got cocky and stops to take a nap while the tortoise kept going. Eventually the tortoise wins the race.
Of course, we are not applying the moral of the story to our algorithm. Instead, image the race is done in a circle, and the hare keeps running. Eventually the hare will lap the tortoise, right?
Applying this to our problem. We can create 2 pointers, representing the hare and tortoise. If the “hare” pointer moves faster than the “tortoise” pointer, and the hare reaches the endpoint first, then we know there’s no circle. However, if we somehow find that the hare and the tortoise pointers point to the same node (where the hare laps the tortoise), then we know this race is done in a circle.
slow to represent these 2 pointers. The algorithm looks like this
if not head or not head.next:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
We want to make sure there’s a
next for fast’s next node, so we can do
.next.next without running into exceptions.
The while loop looks for the “end point “ of the race, where the linked list stops. The if condition checks when the hare laps the tortoise.
We still have the same time complexity O(n) because this is still linear to the length of the linked list.
There you go! Simple problem. If you’re not familiar with the hare and tortoise idea, make sure to at least know that you can use the tracker method and state the limitation. The interviewers want to know that you know there’s some potential fallout with the tracker approach even if you cannot come up with a better one. This is the time to ask for hint or tip even if that means your points get deducted. It’s better than not being able to solve the problem.
Again, if you ever see a “circular linked list” problem, think if we can have a hare and tortoise situation.
Buy my a coffee: https://www.buymeacoffee.com/jonathanckz