# Reverse a Linked List Using Stack

“** Reverse a Linked List Using Stack**” is very popular and technical interview favourite problem based on linked list. Here, we are given a linked list and our task is to reverse the linked list using stack.

**Example:**

Suppose, we need to reverse the following linked list: LINKED LIST: 12 -> 13 -> 14 -> 15 -> 16 After reversing the list: LINKED LIST: 16 -> 15 -> 14 -> 13 -> 12

The steps required to reverse a linked list is as follows:

- If the linked list is empty, return.
- Initialize a stack which contains nodes.
- Push all the nodes in a stack except last nodes of a linked list.
- Make head to the last node of a linked list.
- Now, pop every node in stack and insert them at the end of the newly headed linked list.
- Print the reversed Linked List.

**C++Program to reverse a linked list using stack is as follows:**

/* C++ Program to Reverse a Linked List Using Stack */ #include<bits/stdc++.h> using namespace std; /* Strcutre of node of the Linked List */ typedef struct node { int data; struct node *next; }Node; /* Function to Insert a Node at the end of the Linked List */ void insertEnd(Node **head,int ele) { /* Creating a New Node */ Node *new_node = new Node(); new_node -> data = ele; new_node -> next = NULL; /* Check whether Linked List is empty or not */ /* If Linked List is Empty, new node will become head of the Linked List */ if(*head == NULL) { (*head) = new_node; return; } /* If Linked List is not empty, traverse the complete linked list and points the pointer of the last node of the linked list to the new node */ Node *temp = (*head); while(temp->next != NULL) temp = temp -> next; temp -> next = new_node; } /* Function to Print the Linked List */ void print(Node *head) { Node *temp = head; while(temp != NULL) { cout << temp -> data << " "; temp = temp -> next; } cout<<endl; } /* Function to Reverse a Linked List */ void reverse(Node **head) { /* Create a stack(using STL) of Node structure type */ stack<Node*>st; Node *temp = (*head); /* Insert all the nodes of the Linked List except last node */ while(temp->next != NULL) { st.push(temp); temp = temp -> next; } /* Make Last Node the new head of the linked list */ *head = temp; /* One-by-one pop all the nodes from the linked list and insert at the end of the linked list */ while(!st.empty()) { temp -> next = st.top(); temp = temp -> next; st.pop(); } temp -> next = NULL; } int main() { Node *head = NULL; /* Inserting some nodes to the Linked List */ insertEnd(&head,1); insertEnd(&head,2); insertEnd(&head,3); insertEnd(&head,4); cout<<"Linked List Before Reversing:\n"; print(head); /* Reverse a Linked List */ reverse(&head); cout<<"\nLinked List After Reversing:\n"; print(head); }

Linked List Before Reversing: 1 2 3 4 Linked List After Reversing: 4 3 2 1OUTPUT:

**Related Posts:**

**Reverse a Linked List.****Printing Linked List in Reverse Order without actually reversing the Linked List.****Swap Adjacent Elements of the Linked List.****Count All Occurrences of a Particular Node in a Linked List.****Bubble Sort on Linked List.****Detect a Loop in a Linked List.****Find the Length of the Loop present in the Linked List.****Detect and Remove Loop from a Linked List.****Segregate Even and Odd Nodes of the Linked List.****Delete Complete Linked List.****Delete Nth Node of the Linked List.****Delete without head pointer of the Linked List.****Delete All Occurrences of particular node of the Linked List.****Delete Alternate Nodes of the Linked List.****Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.****Remove Duplicate Nodes from an Unsorted Linked List.****Remove Duplicate Nodes from a Sorted Linked List.****Find Union and Intersection of Two Linked List.****Merge Two Sorted Linked List.****Insert a New Node at the Middle of the Linked List.**