Print a Linked List in Reverse Order
After mastering the four standard operations on a Linked List - Creation, Traversal, Insertion, and Deletion - we will now proceed to the next topic: 'Printing a Linked List in Reverse Order'. It serves as a continuation of our previous discussions. We will build upon the topics and ideas that we have previously explored to further our understanding about Linked List.
We 'll be using recursive approach for the implementation. For this a separate recursive function would be needed. Concept of stack is also implemented for print statement. Let's discuss the algorithm for the same:
Algorithm:
- Create a function printReverse(), which takes 'head' of the Linked List as the parameter.
- Take a temporary node 'cur' and assign it with the head of the list.
- Create a base case which checks if cur==null.
- If base case is TRUE, then function would return.
- If base case is FALSE, then the statements following that base case would be executed.
- Function call statement is defined which contains pointer to the next node.
- Following the function call statement there is a print statement, which would be executed after base case is TRUE, in LIFO manner.
Source Code:
Time Complexity: The time complexity of the function is `O(n)`, where `n` is the number of nodes in the linked list. This is because the function `printReverse` is called recursively for each node in the list until it reaches the end. Each recursive call takes constant time, so the overall time complexity is linear in the number of nodes.
Full Source Code: Code | Reverse Order Printing of Linked List (mycodingnetwork.blogspot.com)
Output:
Video Reference:
Hope you liked this explanation, for any doubt/feedback/improvements/corrections you can comment down in the comment section.