Reversing a linked list (For Beginners)

[2327 views]

Reversing a linked list

A very common data structure Linked list, is a topic that involves the 're-wiring' of links in order to do the required task.
In this article, I will give an intuitive explanation as to how we can reverse a linked list!
The question is super famous and is frequently asked by companies like Amazon, Samsung, Microsoft, etc.

So we are given a reference to the head of a linked list, we need to reverse it.
Let's say that the linked list looks like this:

Now we need to reverse the list by changing only the links between these nodes! This is the re-wiring we need to do

For any linked lists based problem the first thing to keep in mind is that,

When you break a link, do not leave access to a node that you will need. Preserve that.

Lets look at what we need to do for the first wiring.

We need 1 to point to NULL, we can do that by saying head.next = NULL

But that would leave us in a situation where we can never access 2 now! This would be wrong!

Now what if we preserve the 2's location somehow? temp = head.next . Now temp can always tell us where the 2 guy is.

Even if we do a head.next = NULL, we still have access to 2 using temp.

Now I can do the same thing, store 3 in temp1 and make temp.next = head i.e. make 2 point to 1(head)
But making these new pointers again and again is obviously not feasible at all!!
Also we need to move head along with every rewiring for obvious reasons.
We need to try and make use of the same pointer by making it move ahead one step at a time.

Halfway there with the re wirings looks like:

This is exactly what our algorithm for reversing a linked list does.
1. Prev (denoting the previous node at all times) initialized to null.
2. Do the following steps while head!= NULL:
2.1 Save head's current location temp so that it can freely move ahead.
2.2 Make head move ahead, we can do it safely now.
2.3 Make the temp's next point to prev
2.4 Update prev to temp, because this is where the current head has to point now!

Final result looks like: