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

Related Posts:

1. Reverse a Linked List.
2. Printing Linked List in Reverse Order without actually reversing the Linked List.
3. Swap Adjacent Elements of the Linked List.
4. Count All Occurrences of a Particular Node in a Linked List.
5. Bubble Sort on Linked List.
6. Detect a Loop in a Linked List.
7. Find the Length of the Loop present in the Linked List.
8. Detect and Remove Loop from a Linked List.
9. Segregate Even and Odd Nodes of the Linked List.
10. Delete Complete Linked List.
11. Delete Nth Node of the Linked List.
12. Delete without head pointer of the Linked List.
13. Delete All Occurrences of particular node of the Linked List.
14. Delete Alternate Nodes of the Linked List.
15. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
16. Remove Duplicate Nodes from an Unsorted Linked List.
17. Remove Duplicate Nodes from a Sorted Linked List.
18. Find Union and Intersection of Two Linked List.
19. Merge Two Sorted Linked List.
20. Insert a New Node at the Middle of the Linked List.