Reverse Reverse!... A Linked List?
For your next technical interview
After studying linked lists, this very popular question pops up: How do you reverse a linked list? Not just that, but how do you do it in place? The first time I reviewed this question, I had a hard time wrapping my head around it, but it finally clicked!
Let’s get started.
Singly Linked List Review
If you’re not familiar with the basics of a singly linked list, check out my previous article.
The foundation of our singly linked list can be seen on GitHub.
Overview
Our linked list example will be 1 → 2 → 3 → 4.
The result we’re looking for is 1 ← 2 ←3 ←4.
The key thing to remember about a singly linked list is that each node only contains its value and a pointer to the next node. There is no pointer to the previous node. So, we’ll have to keep a variable that holds the reference to the previous node. We’ll also have to keep a variable that holds the reference to the next node.
I’m sure you’re wondering why since each node has a next pointer. As we loop through the list and change the current node’s next pointer value, we lose our next pointer in the iteration. As a result, we’ll have to keep track of the next node to know where we’re going.
Our method will be starting at the beginning of the list and changing the direction of the pointers as we move along the list.
Iterative Setup
Since we’re starting at the beginning of the linked list, our current node is the head of the list. We don’t have a previous value yet, so we’ll set previous to null. Our next reference variable will also be declared but not defined yet.
When we reverse a list, we already know that the last item becomes the first and the first item becomes the last. Knowing this, we can start by swapping the head and tail values.
Note: This code is a continuation of the class Singly Linked List from the gist linked above.
Looping Through the List
There are various ways that you can loop through the linked list: a for loop, a while loop, etc. For the sake of this explanation, I’ll go through it using a while loop.
The meat (and potatoes!) of this question occurs during our loop:
- As we go through the loop, we quickly save the current node’s next pointer into our variable. This is because once we change the next value, we sever ties with it! So we have to save it into our next variable in order to know where to move on to.
- Reverse reverse! We set the current node’s next pointer to the previous node. When we first start,
previousis set tonull. So the initial head value of1now points tonull. This is where we are reversing the values!
3. We’re done with reversing and can move on, so we set the previous node to the current node.
4. And then move the current node to the next node, which is saved under the variable next.
5. Aaand repeat! Check out the next few images to get a feel for what happens in the while loop as we continue.
Notice that our while loop states that we are looping as long as there is a node. Once we get to the tail (final) node, the next variable will be set to the tail’s next property, which is null. The tail’s next property will be set to the previous node, and the previous node is updated to be the current node. The current node is updated to be null. This makes us hop out of the while loop.
Big O
Solving this iteratively results in a time complexity of O(N), where N is the number of nodes since we’re looping through all nodes in the list. The space complexity is O(1) since we’re doing this in place and not using an external data structure.
Check out the complete gist.
I hope that helped! Thanks for reading.
