# Reverse a linked list using stack

The given problem is to reverse a singly linked list using a stack. A singly linked list is a data structure in which each element (node) contains a value and a reference (pointer) to the next node. Reversing a linked list means changing the order of nodes such that the last node becomes the first node, and the first node becomes the last node.

## Problem Statement

We are given a singly linked list, and we need to reverse it using a stack and print the reversed linked list.

## Explanation with Suitable Example

Consider the following singly linked list:

``10 → 20 → 30 → 40 → 50 → 60 → NULL    `` After reversing the linked list using a stack, it becomes:

``60 → 50 → 40 → 30 → 20 → 10 → NULL    `` ## Idea to Solve the Problem

To reverse a singly linked list using a stack, we can follow these steps:

1. Traverse the original linked list and push each node onto the stack.
2. The last node pushed onto the stack will be the new head of the reversed linked list.
3. Pop each node from the stack and set its next pointer to the previously popped node.

## Pseudocode

The following pseudocode outlines the steps to reverse a singly linked list using a stack:

``````function reverse()
create an empty stack
while temp is not the last node (temp.next != null)
push temp onto the stack
move to the next node (temp = temp.next)
set the head and tail of the linked list to the last node (head = tail = temp)
while the stack is not empty
pop a node from the stack (poppedNode = stack.pop())
set the next pointer of the last node to the popped node (tail.next = poppedNode)
move the tail pointer to the popped node (tail = poppedNode)
set the next pointer of the last node to null (tail.next = null)
``````

## Algorithm Explanation

1. If the linked list is empty (head == null), return as there is nothing to reverse.
2. Create an empty stack to store the nodes.
5. Traverse the original linked list using a loop while temp is not the last node (temp.next != null).
6. Inside the loop, push the current node (temp) onto the stack and move to the next node (temp = temp.next).
7. After the loop, set both the head and tail of the linked list to the last node (head = tail = temp).
8. Traverse the stack while it is not empty:
• Pop a node from the stack (poppedNode = stack.pop()).
• Set the next pointer of the last node (tail) to the popped node (tail.next = poppedNode).
• Move the tail pointer to the popped node (tail = poppedNode).
9. After the stack is empty, set the next pointer of the last node to null (tail.next = null), effectively ending the reversed linked list.

## Time Complexity

The time complexity of reversing a linked list using a stack is O(n), where n is the number of nodes in the linked list. In this approach, we traverse the linked list once to push nodes onto the stack and then pop nodes from the stack, which takes linear time.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.