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 <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;
}
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);
    }
}


#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
}



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. Problems like these are good for strengthening your concepts in LinkedList. I would highly recommend you to practice more such problems from Linked List.

Leave a Reply

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