Dada una lista doblemente enlazada de enteros positivos. La tarea es imprimir los datos de la lista doblemente enlazada dada en orden inverso.
Ejemplos :
Input: List = 1 <=> 2 <=> 3 <=> 4 <=> 5 Output: 5 4 3 2 1 Input: 10 <=> 20 <=> 30 <=> 40 Output: 40 30 20 10
Acercarse:
- Tome un puntero para señalar el encabezado de la lista doblemente enlazada.
- Ahora, comience a recorrer la lista vinculada hasta el final.
- Después de llegar al último Node, comience a atravesar en dirección hacia atrás y simultáneamente imprima el Node->datos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to print doubly
// linked list in reverse order
#include <bits/stdc++.h>
using namespace std;
// Doubly linked list node
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// Function to print nodes of Doubly
// Linked List in reverse order
void reversePrint(struct Node** head_ref)
{
struct Node* tail = *head_ref;
// Traversing till tail of the linked list
while (tail->next != NULL) {
tail = tail->next;
}
// Traversing linked list from tail
// and printing the node->data
while (tail != *head_ref) {
cout << tail->data << " ";
tail = tail->prev;
}
cout << tail->data << endl;
}
/* UTILITY FUNCTIONS */
// Function to insert a node at the
// beginning of the Doubly Linked List
void push(struct Node** head_ref, int new_data)
{
// allocate node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
// put in the data
new_node->data = new_data;
// since we are adding at the beginning,
// prev is always NULL
new_node->prev = NULL;
// link the old list off the new node
new_node->next = (*head_ref);
// change prev of head node to new node
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
// move the head to point to the new node
(*head_ref) = new_node;
}
// Driver Code
int main()
{
// Start with the empty list
struct Node* head = NULL;
// Let us create a sorted linked list
// to test the functions
// Created linked list will be 10->8->4->2
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
cout << "Linked List elements in reverse order : " << endl;
reversePrint(&head);
return 0;
}
Java
// Java Program to print doubly
// linked list in reverse order
class Sol
{
// Doubly linked list node
static class Node
{
int data;
Node next;
Node prev;
};
// Function to print nodes of Doubly
// Linked List in reverse order
static void reversePrint( Node head_ref)
{
Node tail = head_ref;
// Traversing till tail of the linked list
while (tail.next != null)
{
tail = tail.next;
}
// Traversing linked list from tail
// and printing the node.data
while (tail != head_ref)
{
System.out.print( tail.data + " ");
tail = tail.prev;
}
System.out.println( tail.data );
}
// UTILITY FUNCTIONS /
// Function to insert a node at the
// beginning of the Doubly Linked List
static Node push( Node head_ref, int new_data)
{
// allocate node
Node new_node = new Node();
// put in the data
new_node.data = new_data;
// since we are adding at the beginning,
// prev is always null
new_node.prev = null;
// link the old list off the new node
new_node.next = (head_ref);
// change prev of head node to new node
if ((head_ref) != null)
(head_ref).prev = new_node;
// move the head to point to the new node
(head_ref) = new_node;
return head_ref;
}
// Driver Code
public static void main(String args[])
{
// Start with the empty list
Node head = null;
// Let us create a sorted linked list
// to test the functions
// Created linked list will be 10.8.4.2
head = push(head, 2);
head = push(head, 4);
head = push(head, 8);
head = push(head, 10);
System.out.print( "Linked List elements in reverse order : " );
reversePrint(head);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 Program to print doubly
# linked list in reverse order
import math
# Doubly linked list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to print nodes of Doubly
# Linked List in reverse order
def reversePrint(head_ref):
tail = head_ref
# Traversing till tail of the linked list
while (tail.next != None):
tail = tail.next
# Traversing linked list from tail
# and print the node.data
while (tail != head_ref):
print(tail.data, end = " ")
tail = tail.prev
print(tail.data)
# UTILITY FUNCTIONS
# Function to insert a node at the
# beginning of the Doubly Linked List
def push(head_ref, new_data):
# allocate node
new_node = Node(new_data)
# put in the data
new_node.data = new_data
# since we are adding at the beginning,
# prev is always None
new_node.prev = None
# link the old list off the new node
new_node.next = head_ref
# change prev of head node to new node
if (head_ref != None):
head_ref.prev = new_node
# move the head to po to the new node
head_ref = new_node
return head_ref
# Driver Code
if __name__=='__main__':
# Start with the empty list
head = None
# Let us create a sorted linked list
# to test the functions
# Created linked list will be 10.8.4.2
head = push(head, 2)
head = push(head, 4)
head = push(head, 8)
head = push(head, 10)
print("Linked List elements in reverse order : ")
reversePrint(head)
# This code is contributed by Srathore
C#
// C# Program to print doubly
// linked list in reverse order
using System;
class Sol
{
// Doubly linked list node
public class Node
{
public int data;
public Node next;
public Node prev;
};
// Function to print nodes of Doubly
// Linked List in reverse order
static void reversePrint( Node head_ref)
{
Node tail = head_ref;
// Traversing till tail of the linked list
while (tail.next != null)
{
tail = tail.next;
}
// Traversing linked list from tail
// and printing the node.data
while (tail != head_ref)
{
Console.Write( tail.data + " ");
tail = tail.prev;
}
Console.WriteLine( tail.data );
}
// UTILITY FUNCTIONS /
// Function to insert a node at the
// beginning of the Doubly Linked List
static Node push( Node head_ref, int new_data)
{
// allocate node
Node new_node = new Node();
// put in the data
new_node.data = new_data;
// since we are adding at the beginning,
// prev is always null
new_node.prev = null;
// link the old list off the new node
new_node.next = (head_ref);
// change prev of head node to new node
if ((head_ref) != null)
(head_ref).prev = new_node;
// move the head to point to the new node
(head_ref) = new_node;
return head_ref;
}
// Driver Code
public static void Main(String []args)
{
// Start with the empty list
Node head = null;
// Let us create a sorted linked list
// to test the functions
// Created linked list will be 10.8.4.2
head = push(head, 2);
head = push(head, 4);
head = push(head, 8);
head = push(head, 10);
Console.Write( "Linked List elements in reverse order : " );
reversePrint(head);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript Program to print doubly
// linked list in reverse order
// Doubly linked list node
class Node {
constructor() {
this.data = 0;
this.next = null;
this.prev = null;
}
}
// Function to print nodes of Doubly
// Linked List in reverse order
function reversePrint(head_ref) {
var tail = head_ref;
// Traversing till tail of the linked list
while (tail.next != null) {
tail = tail.next;
}
// Traversing linked list from tail
// and printing the node.data
while (tail != head_ref) {
document.write(tail.data + " ");
tail = tail.prev;
}
document.write(tail.data + "<br>");
}
// UTILITY FUNCTIONS /
// Function to insert a node at the
// beginning of the Doubly Linked List
function push(head_ref, new_data) {
// allocate node
var new_node = new Node();
// put in the data
new_node.data = new_data;
// since we are adding at the beginning,
// prev is always null
new_node.prev = null;
// link the old list off the new node
new_node.next = head_ref;
// change prev of head node to new node
if (head_ref != null) head_ref.prev = new_node;
// move the head to point to the new node
head_ref = new_node;
return head_ref;
}
// Driver Code
// Start with the empty list
var head = null;
// Let us create a sorted linked list
// to test the functions
// Created linked list will be 10.8.4.2
head = push(head, 2);
head = push(head, 4);
head = push(head, 8);
head = push(head, 10);
document.write("Linked List elements in reverse order : <br>");
reversePrint(head);
</script>
Producción:
Linked List elements in reverse order : 2 4 8 10
Complejidad de tiempo : O (N) donde N no es ningún Node en la lista doblemente enlazada
Espacio Auxiliar: O(N)