LinkedLists 201: Finding the Midpoint
I know. I know. It’s been a while, but it’s finally time to return to everyone’s favorite data structure: linked lists. And to kick off our second foray into linked lists, we are going to get some practice with a fairly common interview question and learn how to find the midpoint of a linked list. Now, this sounds pretty simple (and don’t worry it is!), but there are some stipulations so let’s quickly go over the problem statement and then we can right into solving!
The Problem
The goal of the the midpoint problem is to return the middle node of a linked list. Again, that is pretty simple. You might be wondering, however, what to do if a list has an even number of elements. I mean, how can you find the middle node of an even list? Well, we won’t.
Instead, if a list has an even number of elements, we will return the node at the end of the first half of this list. For example, if it is a list of six nodes, we would be looking to return the third node.
Now that we have that all cleared up, let’s get into solving this problem!
The Solution: A quick note
To solve this problem, we are going to start by keeping a couple things in mind. First, we don’t want to retrieve the size of this list. I know if you wanted to find the midpoint of an array, for example, you could easily call array.length, divide it in half and then grab the middle element. That, however, is not the strategy we want to use to solve this problem.
Second, we only want to iterate through our linked list one time. As we have talked about before, multiple iterations, particularly nested iterations, can really slow down our algorithm. Fortunately for us, there is a way to get our midpoint while only iterating through our list once and so to keep our algorithm quick, we are going to do just that.
The Solution: An Overview
The first step to solving this problem is to create two temporary variables, which for clarity’s sake we are going to call fast and slow.
These variables will both begin by pointing at the first node (or head node) in our list. To be clear, by pointing at, I mean we will assign these variables to the first node in our list.
Then, we will iterate through our list and for every step our loop, we will advance the slow variable by one node and the fast variable by two nodes. This means that our slow variable will ultimately by moving at half the speed of our fast variable.
As soon as we advance our fast variable to the next node, we will want to check to see if the two following nodes are defined. If they are defined, we know that we are still somewhere in the middle of our list and should keep iterating. If one of the variables after fast is undefined, however, we know that we have reached the end of our list and thus, should stop our iteration.
Now, remember how I said that the slow variable is moving half the speed of the fast variable? This means that once fast has reached the end of our list, we know that slow will be pointing at the midpoint of our list and thus, we can return slow and will have successfully retrieved the midpoint.
If you are confused or a bit lost still on how this works, try diagraming this process out yourself. Often, I find the visualization to be helpful in understanding the movement of these two temporary variables!
The Solution: Our Implementation
Hopefully, you have a good understanding of how to implement a solution to this problem after reading the overview above (and if you do, definitely give it a go!), but if you don’t, or if you are lazy and just want to see my implementation, or if you already solved it and want to compare solutions, etc., here’s my solution to the 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
}
Again, I hope this implementation is pretty straightforward after the explanation above, however if you are still feeling unsure about this problem or even our problem solving strategy, try solving this problem on your own. I feel like a broken record every time I repeat this advice, but it’s definitely true: the best way to get better at solving and understanding solutions to these problems is to practice. Good luck and happy coding!
