We have learned to traverse a singly list in forward order. What if problem is to traverse or print a singly linked list in reverse order? For example:
Link list : 1-2->3->4->5->NULL Output should be : 5 4 3 2 1
Since, we have no way to traverse linked list in back ward direction, this becomes an interesting problem.
Brute force solution for traversing linked list in reverse order is to first reverse list, then print it and then again reverse it. Complexity of this approach is O(n). However there two caveats : First we are modifying the original input and second scanning list thrice (two times for reverse and once for printing).
Question is can we not modify list and do it in one scan? Problem here is that last element is to be printed first, then second to last and so on till head of list is printed at last. What is the data structure which gives us such last in first out capability? Great, it’s stack!
Our second approach is to traverse linked list and put all nodes on to stack. Now print elements from stack till it is empty. This method scans list twice (once while putting in stack and next time when printing stack). Other problem with this approach is O(n) extra space is used.
Can we simulate stack using recursion? This will reduce scans to only once. However, there is implicit usage of O(n) space to store stack frames of function calls. Recursive algorithm to print linked list in reverse order :
1. If node is null, return 2. PrintList(node->next) 3. Print node->data;
Code is very simple to implement.
This may sound a very simple problem, but the technique (recursive reverse traversal of singly linked list) is used in many other problems like : Delete a linked list and Find if linked is palindrome or not.
As mentioned above, complexity of recursive method to print linked list in reverse order is O(n) with O(n) implicit space complexity. One note of caution, in production environment, one with explicit stack is preferred over recursion when size of input is unpredictable.
Please write in comments if you find something wrong or want some improvement. Sharing is caring.