Coding Interviews: Solving the “Reverse a Linked List in Place” Problem

A General Note about Coding Interviews

While having a strong grasp of algorithm design and data structures can help you in your software engineering career, these coding interview algorithm problems aren’t necessarily the best reflection of how you’ll perform at your job. They are more of a reflection of your preparation and resources.

As long as companies still use these types of problems, you’ll need to prepare for them.

Problem Source / Inspiration

Glassdoor
Asked by: Google

Problem Description

Reverse a linked list without extra space.

An example of a linked list and its reversal.

Problem Solution

It’s important to analyze and understand all aspects of the problem statement. In this case, the problem statement is short and can be broken into two main components: “Reverse a linked list” and “without extra space.” The first component can be seen in the illustration above. When a prompt refers to a “linked list” without any modifiers or clarification, it is often referring to a singly linked list which is unidirectional. Instead of the nodes being chained 1–2–3, we need them to be chained like 3–2–1.

The second component is a slight twist to the problem. Essentially, the problem is saying reverse this linked list and do it with O(1) space complexity. In other words, do not just create an entirely new linked list that is correctly reversed, but instead, reverse the linked list in place.

Let’s visualize how we’ll accomplish this.

First, you’ll notice the “Temporary Node Storage” on the right side of each step of the reversal. This is an illustration to show that we need to keep a reference to individual nodes. We’re not creating any new nodes; we’re only storing a reference to existing nodes. That way we’ll only take up O(1) memory.

Now let’s take a look at each step with more detail:

1. The first step simply illustrates our initial conditions. There are 3 nodes and we do not have a reference to any particular node.
2. The second step keeps a reference to the “next” node in the list. Since our root node is Node 1, our next node will be Node 2.
3. In Step 3, we reassign where Node 1 is pointing. Initially, it was pointing at Node 2, but we then reassign it to point to null. Note: The illustration shows Node 1 pointing to the same instance of null that Node 3 is pointing to, but that is for brevity. It’s unnecessary to use the same instance, and a new instance of null will be more practical.
4. Step 4 shows how we replace the reference to Node 2 with a reference to Node 3 in our temporary node storage.
5. We then switch Node 2 to point to Node 1, in Step 5.
6. Finally, we arrive at Step 6 where we switch Node 3 to point to Node 2. We do not need to store a reference to any other node because we’ve reached the end of our list.

Once you understand the algorithm logic, translating it into code is relatively trivial.

You’ll notice I created a Node class to create individual nodes of our list. You’ll want to use something like this when you write tests to confirm your solution works, correctly. If you’re new to linked lists, please check out this article I wrote that walks you through the process.

As for the function itself, I chose to use a recursive solution, but an iterative solution with pointers would work as well. The base case is conditional on the absence of a node. If there is no node, the function will return the previous node which will be fully reversed at that point. The recursive case stores a reference to the next node, points the current node’s next property to the previous node, and then recursively invokes the function with the next node and the current node.

And that’s it! Once you understand the algorithm, the code will come naturally.

Conclusion

This pattern of storing a reference to a node in order to consume it later is common. Additionally, this toy problem is also a classic one that has been used for several years in interviews. Familiarizing yourself with this pattern will help you with future problems and add another tool to your toolbelt.

Extra Credit: Solve this same problem iteratively instead of recursively.