Introduction to the problem statement
Given a singly-linked list, print it in reverse order without actually reversing it. The only restriction is that you can’t reverse the original linked list.
(Also see Data Structures)
Let us understand this problem with an example:-
Output -
5 -> 4 -> 3 -> 2 -> 1
According to the problem, we only need to print it in reverse order.
To specify, you must begin printing the data from the tail and work your way up to the head of the list.
To reverse the list itself, refer to this problem.
Before you go further, we recommend you try to implement the problem on your own.
Now that you have understood the problem let us switch to the possible methods to deal with the problem.
Method 1: Using auxiliary space, stack
As we all know, Stack is a powerful Data Structure that follows the LIFO( Last In First Out) principle to deal with the data. This signifies that the most recently added element will come out first.
Source: DevDojo
Similarly, extracting elements from the stack returns them in the reverse order of insertion. As a result of its LIFO trait, a stack can store elements in reverse order of insertion and hence can be utilized to address our problem.
The idea is to traverse the LinkedList from the head to the tail, pushing each traversed element onto the stack as you go. When the traversal is performed, the data from the linked list will be in reverse order in the stack. We can now extract the top element from the stack, print it, and then pop the elements one at a time, repeating the procedure until the stack is empty.
Now that you've devised a concept, let's look at its algorithm and implementation:
Algorithm
- Create an empty stack.
- Traverse the linked list and push each node onto the stack one by one.
- After the traversal is performed, run a loop, in each iteration the topmost element must be printed and then popped out from the stack. Repeat this process until the stack becomes empty.
As a result, we’ve printed the reverse of a linked list without actually reversing it.
Implementation in Java
// Java program to print reverse of a linked list using stack
// Import all the packages
import java.util.*;
import java.io.*;
public class LinkedList{
// head of a list
Node head;
// linked list Node with two fields- data, next
class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
// function to print the reverse
public static void printReverse(Node head){
// if the list is empty return to the call
if(head == null){
return;
}
// Create an empty stack
Stack<Integer> sc = new Stack<>();
// temp will point to the head
Node temp = head;
// Run a loop until the temp points to null
while(temp!=null){
// one by one push each temp.data onto the stack
sc.push(temp.data);
// Update the temp to move ahead
temp = temp.next;
}
// Run a loop until the stack becomes empty
while(!sc.empty()){
// get the top most element
int top = sc.peek();
// print the top element
System.out.print(top + "->");
// delete the printed/top element
sc.pop();
}
System.out.println("null");
}
// Utility function to print the linked list
public static void print(Node head){
Node temp = head;
while(temp!=null){
System.out.print(temp.data + "->");
temp = temp.next;
}
System.out.println("null");
}
// Utility function to add the nodes in a list
public void push(int new_data){
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
// main function
public static void main(String args[])
{
// Construct the linked list 1->2->3->4
LinkedList list = new LinkedList();
list.push(4);
list.push(3);
list.push(2);
list.push(1);
// Print the original list
System.out.println("Given list: ");
print(list.head);
// print the list in reverse order
System.out.println("Print reverse of a linked list in reverse order: ");
printReverse(list.head);
}
}
Output
Given list:
1->2->3->4->null
Print reverse of a linked list in reverse order:
4->3->2->1->null
Complexity Analysis
Time Complexity: If we count the no. of operations we’ve performed through the program will be:
- Traversing of each node - O(N), where N is the number of total nodes in a list.
- Pushing onto the stack - O(1), constant time.
- Printing the stack - O(N), where N is the number of pushed nodes onto the stack.
Hence, the time complexity to print the reverse of a linked list will be O(N) + O(N) + O(1) = o(2N+1) ~ O(N), where N is the total number of nodes in the list.
Space Complexity: Since we are utilizing an additional data structure stack for storing the nodes, space complexity would be O(n), where n is the total number of pushed nodes, i.e., the total nodes in a given linked list.
The approach we’ve discussed above is not optimized in the context of space.
Can you think of a better approach for this?
There is another approach that may not give us a better time complexity yet relieve us not to use auxiliary space.
Let us discuss now: