Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Code in C++
3.2.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
Is stack LIFO or FIFO?
4.2.
What is the purpose of a linked list?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Reverse a Linked List using Stack

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Stacks

Introduction

A linked list is a linear data structure that consists of nodes. Each Node contains a data field and a pointer to the next Node. In Linked List, unlike arrays, elements are not stored at contiguous memory locations but rather at different memory locations. Linked Lists are one of the most fundamental and important data structures having a wide range of applications. Linked Lists are also important from the perspective of interviews as well. In this article we are going to take a look at one such problem

Problem Statement

We were given a linked list. The task is to use an auxiliary Stack to reverse the order of elements in the Linked List.

 

Example 1: 

Input 1: 4 1 3

4->1->3->NULL

 

Output 1: 3 1 4

3->1->4>NULL

 

Example 2:

Input 2: 4 7 8 1 9

4->7->8->1->9->NULL

 

Output 2: 9 1 8 7 4

9->1->8->7->4->NULL

Recommended: Try the Problem yourself before moving on to the solution.

Approach

The idea of this approach is simple: traverse all the nodes one by one from the starting node of the given linked list and push all the values of the nodes into the auxiliary stack. 

We know that the stack Data Structure follows the LIFO(last in first out) order. So, if we extract the content of the stack, we get the last element first, then the second last element and so on, i.e. we get the data in reverse order. 

Finally, we change the linked list data from starting with the reversed data from the stack one by one for all nodes.

Steps:

  1. Declare a stack.
  2. Push all the values of the nodes from starting into the stack.
  3. Change the values of the nodes from the beginning of the linked list with the top element of the stack.
  4. Move to the next node and pop the top element from the stack, and
  5. Repeat steps 3 and 4 while the stack is not empty.

Let’s understand the above approach with an example:

Initially, the curr pointer points to the head of the linked list, and all the nodes are pushed into the stack data structure. 

 

Illustration Image

 

Now we replace, curr->data with the stack.top() element and move the curr pointer to the next node and pop the top element of the stack.

 

Illustration Image

 

Again repeat the above process by replacing curr->data with the stack.top() element and moving the curr pointer to the next node and popping the top element of the stack.

 

Illustration Image

We keep on repeating this step until we reach the end node of the linked list.

 

Illustration Image

 

 

Illustration Image

Now, the stack is empty, and we get the required reversed linked list.

 

Illustration Image

Must Read Stack Operations

Code in C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int x)
    {
        data = x;
        next = NULL;
    }
};

void reverse(Node* head)
{
    stack<int> st;

    Node* curr = head;

    while (curr != NULL)
    {
        st.push(curr->data);
        curr = curr->next;
    }

    curr = head;

    while (!st.empty())
    {
        curr->data = st.top();
        curr = curr->next;
        st.pop();
    }

}

void printList( Node* head, int nodes)
{
    Node* curr = head;

    for (int i = 0; i < nodes; i++)
    {
        cout << curr->data << " ";
        curr = curr->next;
    }

}

int main()
{
    Node* head = NULL;
    head = new Node(4);
    head->next = new Node(7);
    head->next->next = new Node(8);
    head->next->next->next = new Node(1);
    head->next->next->next->next = new Node(9);

    int nodes = 5;

    reverse(head);
    printList(head, nodes);
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output

9 1 8 7 4

 

Complexity Analysis

Time Complexity

O(n), where n is the number of nodes in the given linked list as we are traversing all the nodes at max.

Space complexity

It is O(n) as we are using a stack that contains all the nodes of the linked list.
Must Read  C Program to Reverse a Number

Must Read Python List Operations

Frequently Asked Questions

Is stack LIFO or FIFO?

Stacks operate on the LIFO principle, which states that the element inserted last is the first element to be removed from the list. Whereas, Queues operate on the FIFO principle, which states that the element inserted first is the first element to be removed from the list.

What is the purpose of a linked list?

Linked lists are linear data structures that store information in individual nodes. These nodes contain information as well as a link to the next node in the list. Linked lists are commonly used due to their ease of insertion and deletion.

Conclusion

So, this article discussed the approach to reverse a linked list with the help of stack data structure by using its LIFO order property, examples for a better understanding of the approach and its code in C++.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

You can also consider our Mern Stack Course to give your career an edge over others.

In case of any comments or suggestions, feel free to post them in the comments section. Happy Coding!

Live masterclass