Reversing a linked list

 

Problem

We need to reverse the given singly linked list.

Solution

We will take two pointers temp and next, both pointing to null, initially.
We already have first pointer pointing to the first node of the given linked list.

We will iterate over the liked list until first becomes null i.e, first reaches the end of the list. In each iteration we adjust the pointers but we won’t make any changes to the nodes or the data they contain.

Let’s see how this works step by step and then we will look at the code.

In our case, our linked list has four nodes so there will be 4 iterations which are all same except the first one which might be tricky because in this iteration we make the first node, last, by making it’s next pointer point to null using the initial value of temp pointer.

Step 1: 

 

Step 2:

After step 1, this is what we have:

We will repeat the exact same process in step 2, but this time, the node pointed by first (i.e. node with data 20) won’t get it’s next pointer set to null. It will be pointing to the node 10, instead. Can you figure out why?

Step 3:

After step 2, this is what we have:

Let’s apply the steps on this and see what happens:

Step 4:

This is what we have after step 3:

Now this is our last step (in this case) and we will take care of the null in the next pointer of node 40 and make it the first node of our list and get done with the reversal of the linked list.

 

 

Source Code