Program To Reverse A Linked List Using Stack


In the below article we will see an approach on how to reverse a linked list using stack. In this approach we will see how efficiently the stack can be used to reverse a Linked list.

How>How to reverse a linked list using stack.

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 on how to reverse a linked list using stack.

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 on how to reverse a linked list using stack.

  • 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 on how to reverse a linked list using stack.

Implementation on how to reverse a linked list using stack.

#include <stdio.h>
#include <stdlib.h>
struct linked_list {
   int data;
   struct linked_list *next;
};
int stack[30], top = -1;
struct linked_list* head = NULL;
int printfromstack(int stack[]) {
   printf("\nStack:\n");
   while(top>=0) {
      printf("%d ", stack[top--]);
   }
}
int push(struct linked_list** head, int n) {
   struct linked_list* newnode = (struct linked_list*)malloc(sizeof(struct linked_list));
   newnode->data = n;
   newnode->next = (*head);
   (*head) = newnode;
}
int intostack(struct linked_list* head) {
   printf("Linked list:\n");
   while(head!=NULL) {
      printf("%d ", head->data);
      stack[++top] = head->data;
      head = head->next;
   }
}
int main(int argc, char const *argv[]) {
   push(&head, 10);
   push(&head, 20);
   push(&head, 30);
   push(&head, 40);
   intostack(head);
   printfromstack(stack);
   return 0;
}
#include<bits/stdc++.h>
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<int> 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<<i->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
}
import java.util.*;
class ReverseUsingLL
{
    static class Node
    {
        int data;
        Node next;
    }
    static Node head = null;
    static void push( int new_data)
    {
        Node new_node = new Node();
        new_node.data = new_data;
        new_node.next = (head);
        (head) = new_node;
    }
    static Node reverseList(Node head)
    {
        Stack<Node > stk = new Stack<Node> ();
        Node ptr = head;
        while (ptr.next != null)
        {
            stk.push(ptr);
            ptr = ptr.next;
        }
        /* Pop from stack and replace
        current nodes value */
        head = ptr;
        while (!stk.isEmpty())
        {
            ptr.next = stk.peek();
            ptr = ptr.next;
            stk.pop();
        }
        ptr.next = null;
        return head;
    }
    static void printList(Node head)
    {
        while (head != null)
        {
            System.out.print(head.data + " ");
            head = head.next;
        }   
    }
    public static void main(String[] args)
    {   
        push( 10);
        push( 2);
        push( 5);
        push( 1);
        

        head = reverseList(head);

        printList(head);
    }
}
class stackNode:
    def __init__(self, data):
        self.data = data
        self.next = None
 
class stack:
    def __init__(self):
        self.top = None
 
    def push(self, data):
        if self.top == None:
            self.top = stackNode(data)
            return
        s = stackNode(data)
        s.next = self.top
        self.top = s
 
    def pop(self):
        s = self.top
        self.top =self.top.next
        return s

    def reverse(self):
        cur = self.top
        prev = self.top
        cur = cur.next
        prev.next = None
        while cur:
            succ = cur.next
            cur.next = prev
            prev = cur
            cur = succ
        self.top = prev

    def printList(self):
        s = self.top
        while s:
            print(s.data, end = " ")
            s = s.next

s = stack()
s.push(10)
s.push(2)
s.push(5)
s.push(1)

s.printList()
print()

s.reverse()

s.printList()

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. Here we are declaring an empty stack in which we are using push()to reverse the 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.

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQs

  1. Can a Stack be reversed?
  2. The stack can be reversed in the time complexity of O(1) if we represent the stack internally as a linked list.

  3. How do you reverse a linked list?
  4. A linked list can be reversed using a recursive approach. Where we divide the first node and the rest of the list. Then calling the recursive function for the other part by maintaining the connection.

  5. What is the time complexity to reverse a linked list using stack?
  6. The time complexity to reverse a linked list using stack is O(n).

Leave a Reply

Your email address will not be published. Required fields are marked *