Program to reverse a linked list using Stack

Last Updated : 11 Jan, 2023

Given a linked list. The task is to reverse the order of the elements of the Linked List using an auxiliary Stack.

Examples:

Input : List = 3 -> 2 -> 1
Output : 1 -> 2 -> 3

Input : 9 -> 7 -> 4 -> 2
Output : 2 -> 4 -> 7 -> 9

Algorithm:

Traverse the list and push all of its nodes onto a stack.
Traverse the list from the head node again and pop a value from the stack top and connect them in reverse order.

Below is the implementation of the above approach:

C++

// C/C++ program to reverse linked list 
// using stack 
  
#include <bits/stdc++.h> 
using namespace std; 
  
/* Link list node */
struct Node { 
    int data; 
    struct Node* next; 
}; 
  
/* Given a reference (pointer to pointer) to 
   the head of a list and an int, push a new  
   node on the front of the list. */
void push(struct Node** head_ref, int new_data) 
{ 
    struct Node* new_node = new Node; 
  
    new_node->data = new_data; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 
  
// Function to reverse linked list 
Node *reverseList(Node* head) 
{ 
    // Stack to store elements of list 
    stack<Node *> stk; 
  
    // Push the elements of list to stack 
    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.empty()) { 
        ptr->next = stk.top(); 
  
        ptr = ptr->next; 
        stk.pop(); 
    } 
      
    ptr->next = NULL; 
      
    return head; 
} 
  
// Function to print the Linked list 
void printList(Node* head) 
{ 
    while (head) { 
        cout << head->data << " "; 
        head = head->next; 
    } 
} 
  
// Driver Code 
int main() 
{ 
    /* Start with the empty list */
    struct Node* head = NULL; 
  
    /* Use push() to construct below list  
    1->2->3->4->5 */
    push(&head, 5); 
    push(&head, 4); 
    push(&head, 3); 
    push(&head, 2); 
    push(&head, 1); 
  
    head = reverseList(head); 
  
    printList(head); 
  
    return 0; 
} 

Java

// Java program to reverse linked list  
// using stack  
import java.util.*; 
class GfG  
{  
  
/* Link list node */
static class Node 
{  
    int data;  
    Node next;  
} 
static Node head = null; 
  
/* Given a reference (pointer to pointer) to  
the head of a list and an int, push a new  
node on the front of the list. */
static void push( int new_data)  
{  
    Node new_node = new Node();  
  
    new_node.data = new_data;  
    new_node.next = (head);  
    (head) = new_node;  
}  
  
// Function to reverse linked list  
static Node reverseList(Node head)  
{  
    // Stack to store elements of list  
    Stack<Node > stk = new Stack<Node> ();  
  
    // Push the elements of list to stack  
    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;  
}  
  
// Function to print the Linked list  
static void printList(Node head)  
{  
    while (head != null)  
    {  
        System.out.print(head.data + " ");  
        head = head.next;  
    }  
}  
  
// Driver Code  
public static void main(String[] args)  
{  
    /* Start with the empty list */
    //Node head = null;  
  
    /* Use push() to construct below list  
    1->2->3->4->5 */
    push( 5);  
    push( 4);  
    push( 3);  
    push( 2);  
    push( 1);  
  
    head = reverseList(head);  
  
    printList(head);  
} 
}  
  
// This code is contributed by Prerna Saini. 

Python3

# Python3 program to reverse a linked 
# list using stack  
  
# Link list node  
class Node: 
      
    def __init__(self, data, next): 
        self.data = data 
        self.next = next
  
class LinkedList: 
      
    def __init__(self): 
        self.head = None
          
    # Function to push a new Node in  
    # the linked list  
    def push(self, new_data):  
      
        new_node = Node(new_data, self.head)  
        self.head = new_node 
      
    # Function to reverse linked list  
    def reverseList(self):  
      
        # Stack to store elements of list  
        stk = [] 
      
        # Push the elements of list to stack  
        ptr = self.head  
        while ptr.next != None:  
            stk.append(ptr)  
            ptr = ptr.next
      
        # Pop from stack and replace  
        # current nodes value'  
        self.head = ptr  
        while len(stk) != 0:  
            ptr.next = stk.pop()  
            ptr = ptr.next
          
        ptr.next = None
      
    # Function to print the Linked list  
    def printList(self): 
          
        curr = self.head 
        while curr:  
            print(curr.data, end = " ")  
            curr = curr.next
  
# Driver Code  
if __name__ == "__main__": 
  
    # Start with the empty list 
    linkedList = LinkedList()  
  
    # Use push() to construct below list  
    # 1.2.3.4.5 
    linkedList.push(5)  
    linkedList.push(4)  
    linkedList.push(3)  
    linkedList.push(2)  
    linkedList.push(1)  
  
    linkedList.reverseList()  
  
    linkedList.printList()  
  
# This code is contributed by Rituraj Jain  

C#

// C# program to reverse linked list  
// using stack  
using System; 
using System.Collections.Generic; 
  
class GfG  
{  
  
/* Link list node */
public class Node  
{  
    public int data;  
    public Node next;  
}  
static Node head = null;  
  
/* Given a reference (pointer to pointer) to  
the head of a list and an int, push a new  
node on the front of the list. */
static void push( int new_data)  
{  
    Node new_node = new Node();  
  
    new_node.data = new_data;  
    new_node.next = (head);  
    (head) = new_node;  
}  
  
// Function to reverse linked list  
static Node reverseList(Node head)  
{  
    // Stack to store elements of list  
    Stack<Node > stk = new Stack<Node> ();  
  
    // Push the elements of list to stack  
    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.Count != 0) 
    {  
        ptr.next = stk.Peek();  
        ptr = ptr.next;  
        stk.Pop();  
    }  
    ptr.next = null;  
      
    return head;  
}  
  
// Function to print the Linked list  
static void printList(Node head)  
{  
    while (head != null)  
    {  
        Console.Write(head.data + " ");  
        head = head.next;  
    }  
}  
  
// Driver Code  
public static void Main(String[] args)  
{  
    /* Start with the empty list */
    //Node head = null;  
  
    /* Use push() to construct below list  
    1->2->3->4->5 */
    push( 5);  
    push( 4);  
    push( 3);  
    push( 2);  
    push( 1);  
  
    head = reverseList(head);  
  
    printList(head);  
}  
} 
  
// This code contributed by Rajput-Ji 

Javascript

<script> 
  
      // JavaScript program to reverse linked list 
      // using stack 
      /* Link list node */
      class Node { 
        constructor() { 
          this.data = 0; 
          this.next = null; 
        } 
      } 
      var head = null; 
  
      /* Given a reference (pointer to pointer) to 
         the head of a list and an int, push a new 
         node on the front of the list. */
      function push(new_data) { 
        var new_node = new Node(); 
  
        new_node.data = new_data; 
        new_node.next = head; 
        head = new_node; 
      } 
  
      // Function to reverse linked list 
      function reverseList(head) { 
        // Stack to store elements of list 
        var stk = []; 
  
        // Push the elements of list to stack 
        var ptr = head; 
        while (ptr.next != null) { 
          stk.push(ptr); 
          ptr = ptr.next; 
        } 
  
        // Pop from stack and replace 
        // current nodes value' 
        head = ptr; 
        while (stk.length != 0) { 
          ptr.next = stk[stk.length - 1]; 
          ptr = ptr.next; 
          stk.pop(); 
        } 
        ptr.next = null; 
  
        return head; 
      } 
  
      // Function to print the Linked list 
      function printList(head) { 
        while (head != null) { 
          document.write(head.data + " "); 
          head = head.next; 
        } 
      } 
  
      // Driver Code 
      /* Start with the empty list */
      //Node head = null; 
  
      /* Use push() to construct below list 
      1->2->3->4->5 */
      push(5); 
      push(4); 
      push(3); 
      push(2); 
      push(1); 
  
      head = reverseList(head); 
  
      printList(head); 
        
</script>

Output

5 4 3 2 1

Complexity Analysis:

Time Complexity : O(n), as we are traversing over the linked list of size N using a while loop.
Auxiliary Space: O(N), as we are using stack of size N in worst case which is extra space.

We can reverse a linked list with O(1) auxiliary space. See more methods to reverse a linked list.

ashutoshadhikari

Improve

Python | Queue using Doubly Linked List

Python program to find middle of a linked list using one traversal

Python Matrix Exercises

Python Functions Exercises

Python Lambda Exercises

Python Pattern printing Exercises

Python DateTime Exercises

Python OOPS Exercises

Python Regex Exercises

Python LinkedList Exercises

Python Searching Exercises

Python Sorting Exercises

Python DSA Exercises

Python File Handling Exercises

Python CSV Exercises

Python JSON Exercises

Python OS Module Exercises

Python Tkinter Exercises

Python Web Scraping Exercises

Python Selenium Exercises

Program to reverse a linked list using Stack

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?