Reverse linked list
In last two posts, we got introduction to linked lists and how can we find length of linked list. In those post, we will learn how to reverse linked list. There are two methods to reverse a linked list : Iterative and recursive. By reversing we mean to change the order of linked list where head becomes last node and last node become the head while all the intermediate node start pointing to previous node instead of next node as it was in original linked list. For example, if given list is something like:
Then after reversing, it becomes
Iterative algorithm to reverse linked list
First thing to keep in mind is that we need to keep track of previous of all nodes because we will be connecting node to its previous. Well, since we will be changing next pointer of node, we need a mechanism where we can store next pointer so that we can move forward in linked list. In all we need three pointers : current (pointing to node we are currently at and at which all modifications are done), previous (node before current) and next (node after current). Sequence of steps to be done for reversing a linked list
1. Check if head is null, if yes, return, no need to reverse anything 2. Initialize current to head, previous to null and next as null 3. For each node repeat below steps till current is null: 3.a save next pointer of current i.e. next = current -> next 3.b change next pointer of current to point to previous i.e current->next = previous 3.c move previous to current i.e previous = current 3.d move current to next i.e. current = next 4. Return previous (this will be new head)
Now, since we know the algorithm, let’s go and implement it.
Reverse linked list : Recursive algorithm
Recursive method pegs on fact that if one node is removed, and then rest of linked list is reversed, removed node can be added to tail of reverse list and hence entire list is reversed.
Original list : 1->2->3->4->5->null Remove one node : 1 Remaining list : 2->3->4->5->null Reverse remaining linked list : 5->4->3->2->null Now add removed node 1 to end of list : 5->4->3->2->1->null
Sublist can be reversed with same function written for reversing original list and case for recursion. What should be the terminating condition here? If there is only one node in linked list, don’t do anything and return and that is our terminating condition. Also add a condition to check if there are any node in linked list to start with.
Other thing that should be noted is: we need to add removed node to end of reversed list. Should we always traversed through partially reverse list and add it there? Well, that will be too inefficient. Note that when reversed list is returned, last node of that list is next node of removed node. In above example, last node is 2 which in original list was next node of 1. So, to add removed node to end of list, we can just do
removed_node->next->next = removed_node //Keep in mind we are relying on the fact that removed_node->next is not null in any case. In implementation take care to this fact. If this is violated, we may end up getting null pointer exception
Hence, recursive algorithm is
1. If head of list is null, return 2. Remove first node and reverse remaining list 3. Added removed node to tail of list
Reverse linked list recursive implementation
Complexity of both methods to reverse a linked list is O(n) as we need to traverse each node of linked list in order to reverse it. However, recursive implementation has implicit stack usage which leads to space complexity of O(n) order, where space requirement of iterative method is constant O(1).
Please share if there is something wrong or missing. If you are interested in contributing to website or have an interview experience to share, please contact us.