The in-place reversal of a linked list

tl;dr The trick is to focus on performing the most important logic first. Then, go construct everything around it.

Whenever you are doing anything for the first time with a data structure, do some doodling. Here’s mine for the linked list:

current.nxt = prev

Part 1

In the most basic case, there must be at least two nodes to perform reversal of a list. Now, assume prev variable contains a pointer to the previous node.

From the above diagram, it became clear to me that all I need is to write that one line of code:

Part 2

Take a moment to reflect on Part_1 code. Notice that there are three variables in action: current, current->prev and prev. Before updatingcurrent->next with the value of prev, its value must be stored in another variable. We will name that variable as nextnode and use it in Part_3 below.

Thus, we must add the 2nd line of code before the all important Part_1 code, as seen below:

/*Part_2*/ Node* nextnode = current->next;
/*Part_1*/ current->next = prev;

Part 3

Is that it? No, not yet. Refer to an important assumption about prev we had made in Part 1. Also, we need to move on to other nodes (using the variable current ) in the linked list and reverse them as well.

• For the next iteration, the prevvariable (in Part_1) must have the correct pointer value. So, we update prev with the value in current.
• Once current has been cached in prev, it is now ready to receive the nextnode value.

And so now we have two more lines of code:

/*Part_3*/ prev    = current; 
/*Part_4*/ current = nextnode; 

We will stick all these four lines within a loop, and viola, we are done! Oh wait! There’s one last bit. We need to assign the head to point to the prev (when the loop terminates, prev will point to the tail node). This will complete the list reversal.

Full Code

On several occasions in the past, it was a struggle to write the code for the reversal of a linked list. Not anymore. As is the case always, the important thing is to stay focused on the most important thing. And once you have done that, everything else seems to fall into place, a lot easier.

Keep the main thing the main thing.

Next time, I will review code that reverses a doubly-linked list. Until then, have fun coding!

The only doodle that you need