LinkedLists 202: Is this list a circle?
Now that we are fairly familiar with LinkedLists (if you’re not, check out these blog posts!) let’s take a look at another common linked list problem and see if we can utilize some of our previous knowledge to find the solution!
The Problem
The goal of this problem is to write a function that we detect if a list is circular/has a loop and then return true if it does, and false if not. Before we begin our solution, let’s clarify what we mean by circular.
If you recall, in a normal linked list, we have a tail node that we know if the tail because it points to a value of null. In a circular or looped linked list, however, the tail node will instead point at an earlier node in our list.
Why do we need to detect loops?
Let’s take a look back at our solution to the linked list midpoint problem:
function midpoint(list) {
let slow = list.head
let fast = list head
while (fast.next && fast.next.next) {
slow = slow.next
fast = fast.next.next
}
return slow
}As you can see, our while loop will run until either fast.next or fast.next.next is null. If our linked list is circular, however, this condition will never be met and thus, we will be stuck in an infinite loop. Thus, by detecting circularity, we can avoid this endless loop trap when we run methods like this one on our lists.
Potential Solution?
As you think about how to approach solving this problem, you might consider the idea of using a counter variable. For example, say you loop over the linked list and increment the counter at every node. If the counter reaches a high value of say 10,000 or 15,000, then we can assume that the list is circular. Seems like an okay solution, right?
Let’s look again at the diagram above. If we were to implement the counter solution, we would basically be looping over the same 5 nodes, 2,000 times each… I mean ultimately, you’d get the correct answer, but your solution would not be close to efficient.
On the flip side, what if we had an un-looped list that was 10,001 nodes long or 16,000 nodes long? Then, not only would our solution be slow and inefficient, but also wrong.
If we are not going to use a counter variable, however, then how should we approach solving this problem?
The Solution: Revisiting the ‘Tortoise and the Hare Algorithm’
Again, let’s take a loop back at our midpoint solution above. You can see we used to variables to traverse through our list, fast and slow. Can we do something similar to solve this problem?
Spoilers: we can.
Just like before, we can start both the slow and the fast variables at our head/root node.
function circular(list) {
let slow = list.head
let fast = list.head
}Then, again like before, we can create a while loop to run until fast.next or fast.next.next is null. Then, as loop runs, we can increment our slow variable by one and our fast variable by two.
function circular(list) {
let slow = list.head
let fast = list.head
while (fast.next && fast.next.next) {
slow = slow.next
fast = fast.next.next
//some logic goes here!
}}
Now that we’ve got that set up, let’s consider how we can detect the circularity of our list. Basically, if there is a loop in our list, the fast variable will circle through the loop, loop back around meet up with the slow variable. Thus, when/if the two variables are ever pointing simultaneously at the same node we can infer that our list is circular.
function circular(list) {
let slow = list.head
let fast = list.head
while (fast.next && fast.next.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
return true
}
}
return false
}One thing to note about this solution is that we are directly comparing the two nodes and not the data inside these nodes. If it possible and even likely that two nodes might contain the same data, thus we want to ensure that we are looking at the nodes as a whole when comparing our slow and fast variables!
I hope you’ve found this walkthrough helpful. Honestly, the more I look at linked list problems, the more interesting and fun I find them! As always, I’m going to suggest you try to implement this solution (or one to a similar problem) on your own. The best way to get better at solving algorithms is to practice! Good luck and happy coding!
