How to reverse a linked list in less than 5 minutes

A simple solution to a frequently asked coding problem

The “reversing a linked list” problem has become quite popular, thanks to interviewers at various tech companies. It is a rather simple problem, but you’ll be surprised how many people get confused when trying to implement a solution for the same. Today, we will discuss the problem and implement a solution in Python, all in less than five minutes !

The Problem

Simply put, a linked list is nothing more than a collection of “nodes” or memory locations connected via pointers. The main difference between a linked list and array is that an array consumes a chunk of consecutive memory location while the nodes of a linked list can exist across non-consecutive memory locations and simply connected by a pointer to their location addresses. We can represent a linked list as follows

An empty linked list

Consider a linked list 1->2->3, where 1 is the head of the linked list. When asked to reverse a linked list, we simply change the re-assign the pointer the location of the previous node instead of the next node. When we do this for all the nodes, it will look something like this 1<-2<-3, where 3 is the new head of the list. The logic for this would be as follows:

1. Store the location/address of the next node in a variable (you don’t want to lose this address !)
2. Set the next property of the node to point to the previous node.
3. Set the previous node variable to point to current node.
4. Set the current node variable to point to the next node.
5. Repeat steps 1,2,3&4 until you’ve reached the end of the linked list.

Let’s take a look at the implementation in Python.

Reversing the linked list

That’s it ! Hope this was helpful. Best of luck for that coding interview and stay tuned for more blogs like this one.

References

1. https://www.geeksforgeeks.org/python-program-for-reverse-a-linked-list/