The Blind 75 Leetcode Series: Linked List Cycle

Photo by Chris Ried on Unsplash

Today, we are working on 141. Linked List Cycle

Given , 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 pointer. Internally, is used to denote the index of the node that tail's pointer is connected to. Note that is not passed as a parameter.

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

We have a linked list that might be circular, meaning the 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).

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.

Let’s use and to represent these 2 pointers. The algorithm looks like this

def hasCycle(head):
if not head or not head.next:
return False
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False

We want to make sure there’s a for fast’s next node, so we can do 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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jonathan Chao

Jonathan Chao

219 Followers

I am a software developer who has been in this industry for close to a decade. I share my experience to people who are or want to get into the industry