Reverse linked list | Iterative Solution

In this post, we will see how to reverse linked list iteratively without using recursion.

 

For example,


Input:  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Output: 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

 


 

This first solution uses the “Push” strategy with the pointer re-arrangement hand coded inside the loop to reverse linked list. There’s a slight trickyness in that it needs to save the value of the current->next pointer at the top of the loop since the body of the loop overwrites that pointer.

C++

Download   Run Code

Output:

6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

 


 

Here’s the variation on the above solution that uses MoveNode() to do the work…

C++

Download   Run Code

Output:

6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

 


 

Finally, here’s the previous-current-next strategy. The idea is to use three pointers: next, current, prev and move them down the list. Here, current is the main pointer running down the list, next leads it and prev trails it. For each step, reverse the current pointer and then advance all three to get the next node.

C++

Download   Run Code

Output:

6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

The time complexity of above solutions is O(n) and auxiliary space used by the program is O(1).
 

Also see: Recursive solution to reverse a linked list

 
 
Source: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz