Reverse a linked list using STL stack in C++

In this tutorial, we will learn how to reverse a linked list using stack in STL in C++. Reversing of linked list can be done by many methods but using stacks is the easiest of all. In fact this problem is generally asked in the technical rounds or interviews of companies.

In this problem we have been given a linked list and our task is reverse the linked list. And for the sole purpose we shall be using the Standard Template Library’s Stack.

Reversing of linked list

In here we are using the concept that stack uses LIFO that is Last In First Out. So we shall traverse the linked list once and push the addresses of the nodes in the stack. And then pop the addresses so as to get the addresses in reverse order due to LIFO property. We shall then use a loop to change and reverse the links in linked list starting from the last node of the original linked list.

#include <bits/stdc++.h>
// Including Stack STL
#include <stack>
using namespace std;
// Creating a linked list
struct Linkedlist
{
  int data;
  struct Linkedlist *next;
};
Linkedlist *head = nullptr; // Global head for ease
void insertnode(int);		// Function to insert a node
void print();				// Function to print linked list
int main()
{
  insertnode(2);
  insertnode(4);
  insertnode(6);
  insertnode(8); // Sample insert 2->4->6->8
  print();
  cout << "Reversing the Linked List\n\n";
  stack<struct Linkedlist *> s;
  // Using STL stack to insert the addresses
  // of the nodes in the linked list
  struct Linkedlist *temp = head;
  while (temp != nullptr)
  {
    s.push(temp);
    temp = temp->next;
  }
  temp = head;
  while (temp->next != nullptr)
  {
    temp = temp->next;
  }
  // Treversing till the last node
  head = s.top();
  temp = head;
  s.pop();
  while (s.empty() != 1)
  {
    temp->next = s.top();
    s.pop();
    temp = temp->next;
  }
  temp->next = nullptr;
  // Linked list reversed 8->6->4->2
  print();
  return 0;
}
void insertnode(int a)
{
  struct Linkedlist *node = (struct Linkedlist *)malloc(sizeof(struct Linkedlist));
  node->data = a;
  node->next = nullptr;
  if (head == nullptr)
    head = node;
  else
  {
    Linkedlist *temp = head;
    while (temp->next != nullptr)
    {
      temp = temp->next;
    }
    temp->next = node;
  }
}
void print()
{
  struct Linkedlist *temp = head;
  cout << "Linked list : ";
  if (temp == nullptr)
  {
    cout << "empty" << endl;
    return;
  }
  while (temp != nullptr)
  {
    cout << temp->data << " ";
    temp = temp->next;
  }
  cout << "\n\n";
}

The above code first prints a linked list 2 4 6 8, and then prints “Reversing the Linked List ” and at last prints 8 6 4 2.

Output :
Linked list : 2 4 6 8 

Reversing the Linked List 

Linked list : 8 6 4 2

You may also learn:

• How to check if a given string is binary or not in C++