Given a linked list, print the reverse of it without modifying the list.
Examples:
Input : 1 2 3 4 5 6 Output : 6 5 4 3 2 1 Input : 12 23 34 45 56 67 78 Output : 78 67 56 45 34 23 12
Below are different solutions that are now allowed here as we cannot use extra space and modify the list.
- Recursive solution to print reverse a linked list. Requires extra space.
- Reverse linked list and then print. This requires modifications to the original list.
- A O(n2) solution to print reverse of linked list that first count nodes and then prints k-th node from the end.
In this post, the efficient stack-based solution is discussed.
- First, insert all the elements in the stack
- Print stack till stack is not empty
Note: Instead of inserting data from each node into the stack, insert the node’s address onto the stack. This is because the size of the node’s data will be generally more than the size of the node’s address. Thus, the stack would end up requiring more memory if it directly stored the data elements. Also, we cannot insert the node’s data onto the stack if each node contained more than one data member. Hence, a simpler and efficient solution would be to simply insert the node’s address.
Below is the implementation of the above idea:
C++
// C/C++ program to print reverse of linked list// using stack.#include <bits/stdc++.h>using namespace std;// Link list nodestruct 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 = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}// Counts no. of nodes in linked listint getCount(struct Node* head){ int count = 0; // Initialize count struct Node* current = head; // Initialize current while (current != NULL) { count++; current = current->next; } return count;}// Takes head pointer of the linked list and index// as arguments and return data at indexint getNth(struct Node* head, int n){ struct Node* curr = head; for (int i = 0; i < n - 1 && curr != NULL; i++) curr = curr->next; return curr->data;}void printReverse(Node* head){ // store Node addresses in stack stack<Node*> stk; Node* ptr = head; while (ptr != NULL) { stk.push(ptr); ptr = ptr->next; } // print data from stack while (!stk.empty()) { cout << stk.top()->data << " "; stk.pop(); // pop after print } cout << "\n";}// Driver codeint 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); // Function call printReverse(head); return 0;} |
Java
// Java program to print reverse of linked list// using stack.import java.util.*;class GFG { /* Link list node */ static class Node { int data; 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. */ static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } /* Counts no. of nodes in linked list */ static int getCount(Node head) { int count = 0; // Initialize count Node current = head; // Initialize current while (current != null) { count++; current = current.next; } return count; } /* Takes head pointer of the linked list and index as arguments and return data at index*/ static int getNth(Node head, int n) { Node curr = head; for (int i = 0; i < n - 1 && curr != null; i++) curr = curr.next; return curr.data; } static void printReverse(Node head) { // store Node addresses in stack Stack<Node> stk = new Stack<Node>(); Node ptr = head; while (ptr != null) { stk.push(ptr); ptr = ptr.next; } // print data from stack while (stk.size() > 0) { System.out.print(stk.peek().data + " "); stk.pop(); // pop after print } System.out.println("\n"); } // 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 head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); // Function call printReverse(head); }}// This code is contributed by Arnab Kundu |
Python3
# Python3 program to print reverse of linked list# using stack.# Node of a linked listclass Node: def __init__(self, next=None, data=None): self.next = next self.data = data# 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.def push(head_ref, new_data): new_node = Node() new_node.data = new_data new_node.next = (head_ref) (head_ref) = new_node return head_ref# Counts no. of nodes in linked listdef getCount(head): count = 0 # Initialize count current = head # Initialize current while (current != None): count = count + 1 current = current.next return count# Takes head pointer of the linked list and index# as arguments and return data at indexdef getNth(head, n): curr = head i = 0 while(i < n - 1 and curr != None): curr = curr.next i = i + 1 return curr.datadef printReverse(head): # store Node addresses in stack stk = [] ptr = head while (ptr != None): stk.append(ptr) ptr = ptr.next # print data from stack while (len(stk) > 0): print(stk[-1].data, end=" ") stk.pop() # pop after print print(" ")# Driver code# Start with the empty listhead = None# Use push() to construct below list# 1.2.3.4.5head = push(head, 5)head = push(head, 4)head = push(head, 3)head = push(head, 2)head = push(head, 1)# Function callprintReverse(head)# This code is Contributed by Arnab Kundu |
C#
// C# program to print reverse of linked list// using stack.using System;using System.Collections.Generic;class GFG { /* Link list node */ public class Node { public int data; public 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. */ static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } /* Counts no. of nodes in linked list */ static int getCount(Node head) { int count = 0; // Initialize count Node current = head; // Initialize current while (current != null) { count++; current = current.next; } return count; } /* Takes head pointer of the linked list and index as arguments and return data at index*/ static int getNth(Node head, int n) { Node curr = head; for (int i = 0; i < n - 1 && curr != null; i++) curr = curr.next; return curr.data; } static void printReverse(Node head) { // store Node addresses in stack Stack<Node> stk = new Stack<Node>(); Node ptr = head; while (ptr != null) { stk.Push(ptr); ptr = ptr.next; } // print data from stack while (stk.Count > 0) { Console.Write(stk.Peek().data + " "); stk.Pop(); // pop after print } Console.WriteLine("\n"); } // 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 head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); // Function call printReverse(head); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to print reverse of linked list// using stack./* Link list node */class Node { constructor() { this.data = 0; this.next = null; }};/* Given a reference (pointer to pointer) to the headof a list and an int, push a new node on the frontof the list. */function push(head_ref, new_data){ var new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref;}/* Counts no. of nodes in linked list */function getCount(head){ var count = 0; // Initialize count var current = head; // Initialize current while (current != null) { count++; current = current.next; } return count;}/* Takes head pointer of the linked list and index as arguments and return data at index*/function getNth(head, n){ var curr = head; for (var i = 0; i < n - 1 && curr != null; i++) curr = curr.next; return curr.data;}function printReverse(head){ // store Node addresses in stack var stk = []; var ptr = head; while (ptr != null) { stk.push(ptr); ptr = ptr.next; } // print data from stack while (stk.length > 0) { document.write(stk[stk.length-1].data + " "); stk.pop(); // pop after print } document.write("<br>");}// Driver code// Start with the empty listvar head = null;// Use push() to construct below list// 1.2.3.4.5head = push(head, 5);head = push(head, 4);head = push(head, 3);head = push(head, 2);head = push(head, 1);// Function callprintReverse(head);</script> |
Output
5 4 3 2 1
Time complexity: O(N) where N is number of nodes of linked list
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
