# Print Reverse Of A Linked List Without Actually Reversing it

### Problem statement

Given a singly linked list. Write a function to print it in reverse order. The only restriction is that you can’t reverse the original linked list.

### Problem statement Understanding

Let us understand this problem with an example:
Let’s say we have the given linked list as, According to the problem we need to print it in reverse order. Reverse order means we have to print the values of nodes from right to left.

So the desired output for this linked list will be 5 4 3 2 1.

We need to do this without reversing the given linked list.

Hope that you have understood the problem. Now try to come up with an approach.

If we were allowed to reverse the linked list, then it would be simple. But here we aren’t allowed to do so. So, try to think how we should approach this problem?

### Approach 1 (Using a stack)

Let’s see how a stack works.

It follows the LIFO(last in first out) principle. This means the element inserted most recently will come out first. And similarly, if we extract elements from the stack, we will get them in the reverse order of insertion. This is exactly what we need.

So, due to its LIFO property, a stack is able to store elements in reverse order of their insertion and hence can be used to solve our problem.

We can simply traverse the linked list and push the value stored in the nodes one by one into the stack. When the traversal is complete, we would have the linked list’s data in reverse order in the stack. Now, we can, one by one, extract the top element from the stack and print them and then pop the elements from the stack.

### Algorithm

• Create an empty stack
• Traverse the linked list and push the value in the nodes to the stack.
• After iteration, one by one pop the elements from the stack and print them.
• We would have our linked list printed in reverse order. ### Code Implementation:

```#include
using namespace std;

struct Node {
int val;
Node* next;

Node(int value){
val = value;
next = NULL;
}
};

Node* new_node = new Node(new_val);
}

while(i){
cout<val<<" ";
i = i->next;
}
cout<<"\n";
}

// function to print linked list in
// reverse order using stack
stack st;

while(i){
st.push(i->val);
i = i->next;
}

while(!st.empty()){
cout<

```

### Output

5 4 3 2 1

Time complexity: O(N), as we are doing a complete traversal of the linked list.
Space complexity: O(N), as we are using a stack to store all the nodes.

Where N is the number of nodes in the linked list.

The above algorithm does the work, but it requires extra space. So, can we think of some way to avoid using extra space?

### Approach 2 (Using recursion)

If we traverse a linked list using recursion, we have a choice if we want to print the node before traversing the rest of the nodes or after doing so. So, if we print a node after traversing the remaining nodes, we would achieve our task of printing the linked list in reverse order.

### Algorithm

• Base case - If the linked list is empty do nothing and simply return from the function.
• For the current node, before printing, it recursively call the same function for the next node. This will print all the nodes after the current node.
• Now we just print the current node’s value.

We will have our linked list printed in reverse order. ### Code Implementation:

```
#include
using namespace std;

struct Node {
int val;
Node* next;

Node(int value){
val = value;
next = NULL;
}
};

Node* new_node = new Node(new_val);
}

while(i){
cout<val<<" ";
i = i->next;
}
cout<<"\n";
}

// recusrive function to print
// linked list in reverse order

cout<val<<" ";
}

int main(){

// 1 2 3 4 5

cout<<”Printing Linked list in reverse order:\n”;
// 5 4 3 2 1
}

```