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:

1. If the linked list is empty, return.
2. Initialize a stack which contains nodes.
3. Push all the nodes in a stack except last nodes of a linked list.
4. Make head to the last node of a linked list.
5. Now, pop every node in stack and insert them at the end of the newly headed linked list.
6. 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);
}

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