recursion - Imprima la lista individualmente enlazada en orden inverso

linked-list nodes

Question

De acuerdo, esta fue la pregunta de bonificación en la prueba CMPS 280 en el sureste de Louisiana Univ. Imprima la lista individualmente enlazada en reversa en tres líneas. ¿Algunas ideas?

Answer 1

C implementación de su pregunta de bonificación, en tres líneas:

#include <stdio.h>

struct node {
    int data;
    struct node* next;
};

void ReversePrint(struct node* head) {
    if(head == NULL) return;
    ReversePrint(head->next);
    printf("%d ", head->data);
}

int main()
{
    struct node first;
    struct node second;
    struct node third;

    first.data = 1;
    second.data = 2;
    third.data = 3;

    first.next = &second;
    second.next = &third;

    ReversePrint(&first); // Should print: 3 2 1
    printf("/n");

    return 0;
}

Answer 2

Si tiene permiso para usar otra Estructura de Datos, entonces use una Pila.

Paso 1: recorra la lista vinculada desde el nodo principal y coloque la clave en la pila, hasta que llegue al último nodo. Esto tomará el tiempo de O (n).

Paso 2: saca los elementos de la pila. Esto tomará O (1) vez.

Por lo tanto, el código será

while(head != null){
stack.push(head.val);
head = head.next;
}
while(stack.isEmpty() != true){
stack.pop();
}

Answer 3

En general, cuando solicite ayuda sobre SO, siempre debe intentar primero resolver el problema usted mismo. Luego, si estás atascado, ven aquí con lo que has hecho hasta ahora y muestra claramente cuál es tu problema para maximizar tus posibilidades de obtener ayuda.

Cómo hacer una buena pregunta sobre SO

Sin embargo, dado que es una pregunta del examen pasado y mi respuesta no te ayudará a engañar :), aquí está el pseudo-código de cómo puedes hacerlo recursivamente:

reversePrint(head)
    if head is null then return // Line 1: base case
    reversePrint(head.next)     // Line 2: print the list after head
    print(head.data)            // Line 3: print head