# Program To Reverse A Linked List Using Stack

In the below article we will see an approach on how to reverse a linked list using stack. In this approach we will see how efficiently the stack can be used to reverse a Linked list.

## How>How to reverse a linked list using stack.

In this problem we are given a singly linked list and we have to reverse it using a stack.

Input:

Output:

Now, the main question is how to use a stack to reverse a linked list?

We will look for that under Approach section.

### Approach on how to reverse a linked list using stack.

Let’s think about how a stack works.

It follows the LIFO(last in first out) principle. This means the element inserted at the last will be accessible to us. And similarly, if we remove 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.

Can you think of a case where we don’t need to reverse a linked list?

In case, the linked list is empty or has only one node, reversing the linked list won’t make any change. So, in that case, we don’t reverse it. In all other cases, we need to reverse the linked list.

Let’s see how to implement our idea.

## Algorithm on how to reverse a linked list using stack.

• Check if the linked list is empty or has a single node. If yes, then no need to reverse it and simply return from the function. Otherwise, follow the below steps.
• Declare an empty stack.
• Iterate through the linked list and push the values of the nodes into the stack.
• Now, after the iteration is complete, the linked list is stored in reverse order in the stack.
• Now, start popping the elements from the stack and iterating through the linked list together, and change the values in the nodes by the values we get from the stack.
• Once the stack is empty, we will have the required reversed linked list.

## Implementation on how to reverse a linked list using stack.

```#include <stdio.h>
#include <stdlib.h>
int data;
};
int stack[30], top = -1;
int printfromstack(int stack[]) {
printf("\nStack:\n");
while(top>=0) {
printf("%d ", stack[top--]);
}
}
newnode->data = n;
}
}
}
int main(int argc, char const *argv[]) {
printfromstack(stack);
return 0;
}
```
```#include<bits/stdc++.h>
using namespace std;

struct Node {
int val;
Node* next;

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

// to add a new value at the front of the linked list passed
Node* new_node = new Node(new_val);
}

// if given linked list is empty or
// if it has a single node,
// no need to reverse it

stack<int> st;

// traverse the given linked list and insert all
// the values in the stack st
st.push(i->val);
}

// remove values from stack and
// change the values in the linked list
i->val = st.top();
st.pop();
}
}

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

int main(){

// 1 5 2 10

// 10 2 5 1
}
```
```import java.util.*;
class ReverseUsingLL
{
static class Node
{
int data;
Node next;
}
static void push( int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
}
{
Stack<Node > stk = new Stack<Node> ();
while (ptr.next != null)
{
stk.push(ptr);
ptr = ptr.next;
}
/* Pop from stack and replace
current nodes value */
while (!stk.isEmpty())
{
ptr.next = stk.peek();
ptr = ptr.next;
stk.pop();
}
ptr.next = null;
}
{
{
}
}
public static void main(String[] args)
{
push( 10);
push( 2);
push( 5);
push( 1);

}
}
```
```class stackNode:
def __init__(self, data):
self.data = data
self.next = None

class stack:
def __init__(self):
self.top = None

def push(self, data):
if self.top == None:
self.top = stackNode(data)
return
s = stackNode(data)
s.next = self.top
self.top = s

def pop(self):
s = self.top
self.top =self.top.next
return s

def reverse(self):
cur = self.top
prev = self.top
cur = cur.next
prev.next = None
while cur:
succ = cur.next
cur.next = prev
prev = cur
cur = succ
self.top = prev

def printList(self):
s = self.top
while s:
print(s.data, end = " ")
s = s.next

s = stack()
s.push(10)
s.push(2)
s.push(5)
s.push(1)

s.printList()
print()

s.reverse()

s.printList()

```

#### Output

1 5 2 10

10 2 5 1

Time complexity: O(n), as we are only iterating the linked list.

Space complexity: O(n), as we are using a stack to store all the values.

Here ‘n’ is the number of nodes in the linked list.

Through this article, we learned how a stack can be used to reverse a linked list. Here we are declaring an empty stack in which we are using push()to reverse the linked list. Problems like these are good for strengthening your concepts in LinkedList. I would highly recommend you to practice more such problems from Linked List.

## FAQs

1. Can a Stack be reversed?
2. The stack can be reversed in the time complexity of O(1) if we represent the stack internally as a linked list.

3. How do you reverse a linked list?
4. A linked list can be reversed using a recursive approach. Where we divide the first node and the rest of the list. Then calling the recursive function for the other part by maintaining the connection.

5. What is the time complexity to reverse a linked list using stack?
6. The time complexity to reverse a linked list using stack is O(n).