Reverse a linked list using Stack

The idea is to store the all the nodes in the stack then make a reverse linked list.

Follow the steps below to solve the problem:

Store the nodes(values and address) in the stack until all the values are entered.
Once all entries are done, Update the Head pointer to the last location(i.e the last value).
Start popping the nodes(value and address) and store them in the same order until the stack is empty.
Update the next pointer of last Node in the stack by NULL.

Below is the implementation of the above approach:

C++

// C++ program for above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

// Create a class Node to enter values and address in the
// list
class Node {
public:
    int data;
    Node* next;
      Node(int x) {
        data = x;
         next = NULL;
    }
};

// Function to reverse the linked list
void reverseLL(Node** head)
{
    // Create a stack "s" of Node type
    stack<Node*> s;
    Node* temp = *head;
    while (temp->next != NULL) {
        // Push all the nodes in to stack
        s.push(temp);
        temp = temp->next;
    }
    *head = temp;
    while (!s.empty()) {
        // Store the top value of stack in list
        temp->next = s.top();
        // Pop the value from stack
        s.pop();
        // update the next pointer in the list
        temp = temp->next;
    }
    temp->next = NULL;
}

// Function to Display the elements in List
void printlist(Node* temp)
{
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

// Program to insert back of the linked list
void insert_back(Node** head, int value)
{

    // we have used insertion at back method to enter values
    // in the list.(eg: head->1->2->3->4->Null)
    Node* temp = new Node(value);
    temp->next = NULL;

    // If *head equals to NULL
    if (*head == NULL) {
        *head = temp;
        return;
    }
    else {
        Node* last_node = *head;
        while (last_node->next != NULL)
            last_node = last_node->next;
        last_node->next = temp;
        return;
    }
}

// Driver Code
int main()
{
    Node* head = NULL;
    insert_back(&head, 1);
    insert_back(&head, 2);
    insert_back(&head, 3);
    insert_back(&head, 4);
    cout << "Given linked list\n";
    printlist(head);
    reverseLL(&head);
    cout << "\nReversed linked list\n";
    printlist(head);
    return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java program for above approach
import java.util.*;

class GFG {
    // Create a class Node to enter values and address in
    // the list
    static class Node {
        int data;
        Node next;
          Node(int x) {
            data = x;
              next = null;
        }
    };
    static Node head = null;
    // Function to reverse the linked list
    static void reverseLL()
    {

        // Create a stack "s" of Node type
        Stack<Node> s = new Stack<>();
        Node temp = head;
        while (temp.next != null) {
            // Push all the nodes in to stack
            s.add(temp);
            temp = temp.next;
        }
        head = temp;
        while (!s.isEmpty()) {
            // Store the top value of stack in list
            temp.next = s.peek();
            // Pop the value from stack
            s.pop();
            // update the next pointer in the list
            temp = temp.next;
        }
        temp.next = null;
    }

    // Function to Display the elements in List
    static void printlist(Node temp)
    {
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }

    // Program to insert back of the linked list
    static void insert_back(int value)
    {
        // we have used insertion at back method to enter
        // values in the list.(eg: head.1.2.3.4.Null)
        Node temp = new Node(value);
        temp.next = null;
        // If *head equals to null
        if (head == null) {
            head = temp;
            return;
        }
        else {
            Node last_node = head;
            while (last_node.next != null)
                last_node = last_node.next;
            last_node.next = temp;
            return;
        }
    }

    // Driver Code
    public static void main(String[] args)
    {
        insert_back(1);
        insert_back(2);
        insert_back(3);
        insert_back(4);
        System.out.print("Given linked list\n");
        printlist(head);
        reverseLL();
        System.out.print("\nReversed linked list\n");
        printlist(head);
    }
}

// This code is contributed by Aditya Kumar (adityakumar129)

Python

# Python code for the above approach

# Definition for singly-linked list.


class ListNode:
    def __init__(self, val = 0, next=None):
        self.val = val
        self.next = next


class Solution:

    # Program to reverse the linked list
    # using stack
    def reverseLLUsingStack(self, head):

        # Initialise the variables
        stack, temp = [], head

        while temp:
            stack.append(temp)
            temp = temp.next

        head = temp = stack.pop()

        # Until stack is not
        # empty
        while len(stack) > 0:
            temp.next = stack.pop()
            temp = temp.next

        temp.next = None
        return head


# Driver Code
if __name__ == "__main__":
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
    print("Given linked list")
    temp = head
    while temp:
        print(temp.val, end=' ')
        temp = temp.next
    obj = Solution()
    print("\nReversed linked list")
    head = obj.reverseLLUsingStack(head)
    while head:
        print(head.val, end=' ')
        head = head.next

// C# program for above approach
using System;
using System.Collections.Generic;

class GFG {

    // Create a class Node to enter
    // values and address in the list
    public class Node {
        public int data;
        public Node next;
          public Node(int x) {
            data = x;
        }
    };
    static Node head = null;

    // Function to reverse the
    // linked list
    static void reverseLL()
    {

        // Create a stack "s"
        // of Node type
        Stack<Node> s = new Stack<Node>();
        Node temp = head;

        while (temp.next != null) {

            // Push all the nodes
            // in to stack
            s.Push(temp);
            temp = temp.next;
        }
        head = temp;

        while (s.Count != 0) {

            // Store the top value of
            // stack in list
            temp.next = s.Peek();

            // Pop the value from stack
            s.Pop();

            // Update the next pointer in the
            // in the list
            temp = temp.next;
        }
        temp.next = null;
    }

    // Function to Display
    // the elements in List
    static void printlist(Node temp)
    {
        while (temp != null) {
            Console.Write(temp.data + " ");
            temp = temp.next;
        }
    }

    // Function to insert back of the
    // linked list
    static void insert_back(int val)
    {

        // We have used insertion at back method
        // to enter values in the list.(eg:
        // head.1.2.3.4.Null)
        Node temp = new Node(val);
        temp.next = null;

        // If *head equals to null
        if (head == null) {
            head = temp;
            return;
        }
        else {
            Node last_node = head;

            while (last_node.next != null) {
                last_node = last_node.next;
            }
            last_node.next = temp;
            return;
        }
    }

    // Driver Code
    public static void Main(String[] args)
    {
        insert_back(1);
        insert_back(2);
        insert_back(3);
        insert_back(4);
        Console.Write("Given linked list\n");

        printlist(head);
        reverseLL();

        Console.Write("\nReversed linked list\n");
        printlist(head);
    }
}

// This code is contributed by gauravrajput1

Javascript

<script>
// javascript program for above approach

// Create a class Node to enter 
// values and address in the list
 class Node 
{
     constructor(x){
    this.data = x;
    this.next = null;
}
}
var head = null;
// Function to reverse the 
// linked list
function reverseLL()
{   
    
    // Create a stack "s" 
    // of Node type
    var s = []; 
    var temp = head;
    while (temp.next != null) 
    {
        
        // Push all the nodes 
        // in to stack
        s.push(temp); 
        temp = temp.next;
    }
    head = temp;
  
    while (s.length!=0) 
    {
        
        // Store the top value of
        // stack in list
        temp.next = s.pop(); 
      
      
      
        // update the next pointer in the
        // in the list
        temp = temp.next; 
    }
    temp.next = null;
}

// Function to Display 
// the elements in List
function printlist(temp) 
{
    while (temp != null) 
    {
        document.write(temp.data+ " ");
        temp = temp.next;
    }
}

// Program to insert back of the 
// linked list
function insert_back(  value)
{ 

    // we have used insertion at back method
    // to enter values in the list.(eg:
    // head.1.2.3.4.Null)
    var temp = new Node(value);
    temp.next = null;
    
    // If *head equals to null
    if (head == null) 
    {
      head = temp;
      return;
    }
    else 
    {
      var last_node = head;
      while (last_node.next != null) 
      {
        last_node = last_node.next;
      }
      last_node.next = temp;
      return;
    }
}

// Driver Code

        insert_back(1);
        insert_back(2);
        insert_back(3);
        insert_back(4);
        document.write("Given linked list\n");
        printlist(head);
        reverseLL();
        document.write("<br/>Reversed linked list\n");
        printlist(head);

 // This code is contributed by umadevi9616 
</script>

Output

Given linked list
1 2 3 4 
Reversed linked list
4 3 2 1

Time Complexity: O(N), Visiting every node of the linked list of size N.
Auxiliary Space: O(N), Space is used to store the nodes in the stack.

Reverse a Linked List

Given a pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.

Examples:

Input: Head of following linked list
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULL

Input: Head of following linked list
1->2->3->4->5->NULL
Output: Linked list should be changed to,
5->4->3->2->1->NULL

Input: NULL
Output: NULL

Input: 1->NULL
Output: 1->NULL

Reverse a linked list using Stack

Reverse a Linked List

Categories

Contact US

Reverse a linked list using Stack

Reverse a Linked List

Similar Reads

Categories

Contact US