Reversing a singly linked list is one of those things that’s
super easy to implement but can be tricky at first to actually implement – especially if you’re new to linked lists in
general. At the same time, it’s definitely an algorithm that you should understand.
Besides there of course being use cases for it in dev related purposes, it’s
also the focus of common teasers that you’ll find in interview questions. Simply
put, regardless of whether or not you have an immediate need to utilize this
algorithm, it’s one that any coder should have handy in their back pocket.
The goal of this post is to make it as clear as possible for you to grasp and visualize the method of linked list reversing. As you read along you might find it helpful to also watch
the following video (as the example in the video is the same as talked about in
this post):
Let’s start with a very simple singly linked list:
Yup, nothing fancy about this list. Four integers are linked
together (1 -> 2 -> 3 -> 4) – 1
at the head of the list, 4 at the end. What we want is for the order to become reversed: 4 -> 3 -> 2 -> 1
– putting 4 at the head of the list.
Let’s get into how we’re going to set up our reversal code. We’ll
assume that we’re writing a function which accepts a ‘pointer’ to the head of
the linked list. At the beginning of our function we’ll initialize 3 pointers: previous,
current,
and next.
These pointers will be used so we can keep track of node states during the
reversal.
ListNode previous = null;
ListNode current = head;
ListNode next = head;
ListNode current = head;
ListNode next = head;
Our previous
pointer is currently set to null.
This makes sense because we haven’t even performed 1 iteration of our reversing
loop, so why would previous be set
to anything? Then we set current to head
– even at the start we’re positioned at the head aka first node, so current
should be set to something. Finally we
got our next pointer, currently set
to head as well, and, as long as head wasn’t null to begin with, will
ensure that the below while loop runs at least 1 iteration:
while(head != null) {
}
}
Easy enough so far, right? Now we have to start to work
out the code we’ll have inside our loop.
Let’s pretend we’re just starting and running for one
iteration – the second line of code within our loop is going to overwrite the next pointer on our current node, but we’ll need to reference
that pointer later on so we can keep traversing the linked list – so we’ll
store and preserve that in next for
future use. The following line will set next
to point to node1:
next = current.next;
Now we get to the part where we’re actually linking our current node up to our previous node. At this stage, current is referencing the head node
(node1) and we’re going to link node1’s
next up to prev (right now being
null).
current.next = prev;
Now we’ll update prev
so that it references current (so
prev will point to node1):
prev = current;
And then finally we set current
to next (in this case current will point to node2)
current = next;
By the end of the iteration, node1 will point to null,
and we’ve set our pointers up so that we’re ready to work on linking node2’s next to node1.
I mentioned earlier that in this scenario were writing a
function which will return the value of the new ‘head’ node. As for our return value – what are we going to return
to represent our new head? Just by
visually inspecting the animation we can see that it wouldn’t make sense to
return either current or next since by the end of the process
both of these will hold a null value. We’ll have to return prev since that will always contain the
last item in the list right before null.
Putting it all together, we have the following reversing
method in java (which, being as simple as it is, is easily portable to other
languages):
