Dada una lista enlazada, la impresión inversa de la misma sin modificar la lista.
Ejemplos:
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
A continuación se muestran diferentes soluciones que ahora están permitidas aquí, ya que no podemos usar espacio adicional y modificar la lista.
- Solución recursiva para imprimir de forma inversa una lista enlazada . Requiere espacio adicional.
- Lista enlazada inversa y luego imprimir. Esto requiere modificaciones a la lista original.
- Solución AO(n 2 ) para imprimir el reverso de la lista enlazada que primero cuenta los Nodes y luego imprime el k-ésimo Node desde el final.
En esta publicación, se analiza la solución eficiente basada en pilas.
- Primero, inserte todos los elementos en la pila
- Imprimir pila hasta que la pila no esté vacía
Nota: En lugar de insertar datos de cada Node en la pila, inserte la dirección del Node en la pila. Esto se debe a que el tamaño de los datos del Node generalmente será mayor que el tamaño de la dirección del Node. Por lo tanto, la pila terminaría requiriendo más memoria si almacenara directamente los elementos de datos. Además, no podemos insertar los datos del Node en la pila si cada Node contiene más de un miembro de datos. Por lo tanto, una solución más simple y eficiente sería simplemente insertar la dirección del Node.
A continuación se muestra la implementación de la idea anterior:
C++
// C/C++ program to print reverse of 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
= (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 list
int 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 index
int 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 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);
// 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 list
class 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 list
def 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 index
def getNth(head, n):
curr = head
i = 0
while(i < n - 1 and curr != None):
curr = curr.next
i = i + 1
return curr.data
def 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 list
head = None
# 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
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 head
of a list and an int, push a new node on the front
of 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 list
var 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);
</script>
Producción
5 4 3 2 1
Complejidad temporal: O(N) donde N es el número de Nodes de la lista enlazada
Espacio auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por DevanshuAgarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA