Dada una lista enlazada, imprima el reverso usando una función recursiva. Por ejemplo, si la lista enlazada dada es 1->2->3->4, entonces la salida debería ser 4->3->2->1.
Tenga en cuenta que la pregunta es solo sobre la impresión del reverso. Para invertir la lista en sí, vea este
Nivel de dificultad: Novato
Algoritmo:
printReverse(head) 1. call print reverse for head->next 2. print head->data
Implementación:
C
// C program to print reverse
// of a linked list
#include<stdio.h>
#include<stdlib.h>
// Link list node
struct Node
{
int data;
struct Node* next;
};
// Function to reverse the linked list
void printReverse(struct Node* head)
{
// Base case
if (head == NULL)
return;
// Print the list after head node
printReverse(head->next);
// After everything else is printed,
// print head
printf("%d ", head->data);
}
// UTILITY FUNCTIONS
/* Push a node to linked list.
Note that this function
changes the head */
void push(struct Node** head_ref,
char new_data)
{
// Allocate node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
// Put in the data
new_node->data = new_data;
// Link the old list off the
// new node
new_node->next = (*head_ref);
// Move the head to point to the
// new node
(*head_ref) = new_node;
}
// Driver code
int main()
{
// Create linked list 1->2->3->4
struct Node* head = NULL;
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
printReverse(head);
return 0;
}
Producción:
4 3 2 1
Complejidad de tiempo: O(n)
Complejidad espacial : O (n) para la pila de llamadas desde que se usa la recursividad
¡Consulte el artículo completo sobre Imprimir el reverso de una lista vinculada sin realmente revertir para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA