Why is “Reverse a given Linked List” such a good question?

Let’s talk about why reversing a linked list is a great question, what it teaches us, and how we go about solving it.

Image by Author

In your data structure journey, you must have encountered a question that asks you to reverse a given linked list. If you haven’t yet come across this question, you surely haven’t practised enough questions on this simple but useful data structure. In this article, I will describe the problem at hand, why it’s a good problem and how we can solve it.

Some background on Linked Lists

A regular, singly linked list is a linear data structure. Items inside a linked list follow a sequence or a linear path. Any given node in the linked list holds some data inside itself and a pointer to the next node.

Linked List Data Structure (illustration by author)

In memory, these nodes can be at different memory locations that may or may not be contiguous. Since these nodes are scattered throughout the memory, we need something to tell us where the current node’s next node or its successor is.

This “something” is called a “pointer”. These pointers can store the memory address of their successor nodes which now makes it possible for us to form a sequence or order of nodes even when they are not present in a contiguous fashion in the memory.

But, why Reverse a Linked List?

At first, it may seem like a simple problem. Which it is . . . given that you know your way around pointers. All the operations or algorithms you can apply on linked lists depend on your understanding of the pointers. If you can manipulate the pointers in a clever way, you can master this data structure fairly easily.

Let’s see the input -

Input List

And the output that is expected -

Output List

Basically, your head node becomes the tail(last node), the older tail node now becomes your head node, and every pointer is reversed.

Let’s Reverse!

If you are familiar with linked list traversals, this should be easy to understand. Normally, to traverse a linked list we start at the head node, read its data or print it, and then move to the next node using the pointer and read its data.

We repeat this process until the last node is reached, which will point to
“None”, since there is no next node. This question really tests your pointer manipulation skills & the steps go something like this -

• Traverse the list while keeping track of the current node, its previous node, and its next node.
• Make the current node point to its previous node. Then move to the next node and make its pointer point to its previous node and so on.
• The important thing to know is once you set the pointer of the first node to its previous node i.e “None”, you will not be able to traverse further unless you keep a reference to the actual next node. This may sound complicated, but let’s take a look at the code (python)—

Function to reverse a given LinkedList

• At the start, the prev_node is None since there is no prev node for the first node i.e the head.
• We loop while cur_node exists.
• Set the reference to the actual next node, as we won’t be able to traverse to the next node after we make it point to the previous node.
• Make the pointer of cur_node point to its prev_node.
• Now the cur_node becomes our prev_node.
• Use the reference we saved and set that as the cur_node.
• Set the prev_node as the new head.

The solution is quite neat and makes total sense when you finally understand it. This question is a great example of things that look daunting at first, but aren’t always so sophisticated in nature.

Thanks for reading!

I hope this brief post on reversing linked lists was helpful & interesting to read. Also, special thanks to the awesome people who follow me on this platform. I really appreciate it ❤

recommended posts —

Extracting Synonyms (similar words) from text using BERT & NMSLIB

Most Asked Interview Questions in Python/Django