The linked list reversal algorithm can be difficult to understand without visuals. So…here are some visuals. First I'll show only the algorithm's raw logic, and then I'll sync the animation to actual code. Finally, after we fully understand everything, we'll add it as a class method to a real example.
What is a reversed linked list?
Reversing a list means taking each node's next pointer and swapping it from the node to the right, to the node on the left.
Essentially the head becomes the tail and the tail becomes the head. To be extra clear I'm not talking about doubly linked lists in this article.
Flipping without orphaning
The trick to the algorithm is saving a reference to the next node in the sequence before we flip the pointer. If we flip the pointer too soon, we'd break the chain and have nowhere to jump for the next iteration of the loop.
This animation is the crux of it all. If you understand the sequence here logically, the code is just a simple translation. Make sure to watch it a few times before moving on.
The code
This code links exactly to the animation above, check it out and then look at the next gif that syncs them.
We're given a node, the head of a linked list, and we immediately set it as our curr node. In your code, you can call it current, I only called it curr so it would be legible in a gif. Anyway, the only other node we know prior to the loop is prev, which is null. Our loop will keep going as long as curr is a node and not null. The first step of each loop is assigning out the next node while curr.next still points to it.
And don't forget we must return our previous at the end, because if we don't save that pointer somewhere, we'll have no way to access the new head of our linked list.
Don't confuse the next node, with the .next property.
Syncing the code to the animation
The real way to understand it is to see it in action:
I can't speak for you, but I only really understood this algorithm once I drew it out. I hope that seeing it next to the code really helps things click. I think that visually understanding these algorithms is so important. Otherwise, you only remember what to write, but not why you wrote it.
One quick refactor
Before we actually apply this code to a Linked List class, let's make one small change. The code above works, but it's a little wasteful. Visually, it makes a lot of sense to hold off on declaring the next node until the loop starts. However, that means we are recreating a variable over and over again for no reason. We should declare it once outside of the loop with the rest of the nodes. To convey that it doesn't really exist yet, we could leave it undefined. This differentiates it from prev which we know always starts as null by design.
However, you'll almost always see it set to null. It's functionally the same as leaving it undefined, but it looks more visually consistent. With that change, this is the final code that most people use:
Now that you know how the code truly works, you'll never forget it.
A class example
Alright, with the core concept out of the way, let's plug it into some code. Here's a simple Node and LinkedList class:
Obviously, we could get more complex with it, but these two methods are really all we need. Here's our starting code:
1-> 2-> 3-> 4
Now, we could use our code as is, but it would be a little clunky:
4-> 3-> 2-> 1
Let's streamline it a bit. Instead of padding in a head node, let's use this.head directly. I'll still return it too, because why not. Ok, so here's the whole thing:
1-> 2-> 3-> 4 Reverse it! 4-> 3-> 2-> 1
And there you have it! Now, in an interview, they probably won't bother with the whole class, but like always, I think it's helpful to see things in action. Algorithms are so tricky, but by breaking them down logically, I hope you got a better understanding of them.
Happy coding everyone,
Mike