Reversing a Linked List

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;

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):