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