Program To Reverse A Linked List Using Stack

Problem Statement

In this problem we are given a singly linked list and we have to reverse it using a stack.

Input:

Output:

Now, the main question is how to use a stack to reverse a linked list?
We will look for that under Approach section.

Approach

Let’s think about how a stack works.

It follows the LIFO(last in first out) principle. This means the element inserted at the last will be accessible to us. And similarly, if we remove elements from the stack, we will get them in the reverse order of insertion. This is exactly what we need. So, due to its LIFO property, a stack is able to store elements in reverse order of their insertion and hence can be used to solve our problem.

Can you think of a case where we don’t need to reverse a linked list?
In case, the linked list is empty or has only one node, reversing the linked list won’t make any change. So, in that case, we don’t reverse it. In all other cases, we need to reverse the linked list.

Let’s see how to implement our idea.

Algorithm

• Check if the linked list is empty or has a single node. If yes, then no need to reverse it and simply return from the function. Otherwise, follow the below steps.
• Declare an empty stack.
• Iterate through the linked list and push the values of the nodes into the stack.
• Now, after the iteration is complete, the linked list is stored in reverse order in the stack.
• Now, start popping the elements from the stack and iterating through the linked list together, and change the values in the nodes by the values we get from the stack.
• Once the stack is empty, we will have the required reversed linked list.

Dry Run

Implementation

#include
using namespace std;

struct Node {
    int val;
    Node* next;

    Node(int value){
        val = value;
        next = NULL;
    }
};

// to add a new value at the front of the linked list passed
void push_front(Node** head, int new_val){
    Node* new_node = new Node(new_val);
    new_node->next = *head;
    *head = new_node;
}

void reverse(Node** head){
    // if given linked list is empty or
    // if it has a single node,
    // no need to reverse it
    if(*head == NULL || (*head)->next == NULL) return;

    stack st;

    // traverse the given linked list and insert all
    // the values in the stack st
    for(Node* i= *head; i!=NULL; i=i->next){
        st.push(i->val);
    }

    // remove values from stack and
    // change the values in the linked list
    for(Node* i= *head; i!=NULL; i=i->next){
        i->val = st.top();
        st.pop();
    }
}

void printList(Node* head){
    Node* i = head;
    while(i){
        cout<val<<" ";
        i = i->next;
    }
    cout<<"\n";
}

int main(){
    Node* head = NULL;

    push_front(&head, 10);
    push_front(&head, 2);
    push_front(&head, 5);
    push_front(&head, 1);

    printList(head);
    // 1 5 2 10

    reverse(&head);

    printList(head);
    // 10 2 5 1
}

Output

1 5 2 10
10 2 5 1

Time complexity: O(n), as we are only iterating the linked list.
Space complexity: O(n), as we are using a stack to store all the values.

Here 'n' is the number of nodes in the linked list.

Through this article, we learned how a stack can be used to reverse a linked list. Problems like these are good for strengthening your concepts in LinkedList. I would highly recommend you to practice more such problems from Linked List.