c - simple - invertir lista enlazada java

Invertir lista enlazada recursivamente sin usar ninguna variable nueva

Question

En una entrevista de trabajo, me pidieron que escribiera una función en C que recursivamente invierta una lista vinculada, devuelva el nuevo primer nodo y no use ningún nodo nuevo.

¿Cómo puedes hacer esto?

Answer 1

Aquí está la idea general, en un lenguaje agnóstico con sintaxis tipo C:

Node invert(Node list, Node acc) {
    if (list == null)
        return acc;
    Node next = list.next;
    list.next = acc;
    return invert(next, list);
}

La función anterior recibe el primer nodo de la lista que se invertirá y el valor acumulado hasta el momento, y devuelve el encabezado de la lista invertida recientemente: la inversión de los nodos se realiza en el lugar, no se asigna espacio adicional (además de un local variable en la pila). Llámalo así:

invert(firstNodeOfList, null);

Este es un ejemplo de una recursividad final: el resultado se recopila en el parámetro acc , y cuando regresa cada llamada recursiva, no queda nada por hacer, solo devuelve el valor acumulado.

ACTUALIZAR:

En un lenguaje funcional es más fácil y más natural escribir una función para invertir una lista sin usar una variable local, por ejemplo, observe el siguiente código en Scheme: tiene un inconveniente, que creará un nuevo nodo de lista al invocar el procedimiento de cons . :

(define (invert lst acc)
  (if (empty? lst)
      acc
      (invert (rest lst)
              (cons (first lst) acc))))

(invert ''(1 2 3 4 5) ''())
> ''(5 4 3 2 1)

En pocas palabras: o bien crea un nuevo nodo o crea una nueva variable local en cada llamada recursiva, pero a menos que el lenguaje de programación ofrezca una expresión para la ejecución secuencial y el compilador garantice el orden de evaluación (vea la respuesta de @WillNess) no puede eliminar ambos y tiene un algoritmo de trabajo. Mejor ir a lo seguro y usar una variable temporal para hacer cumplir la orden de evaluación y obtener siempre los resultados correctos.

Answer 2

Entonces, la variación en la respuesta de Óscar López aquí es

Node invert(Node list, Node acc) 
{
    if (!list) 
        return acc; 
    return invert(list.next, ((list.next=acc),list));
}

La secuencia de expresiones (a,b) devuelve su último valor y se evalúa de izquierda a derecha.

Esto solo funcionará para los compiladores que garantizan el orden de evaluación de los argumentos de la función de izquierda a derecha . Si es de derecha a izquierda , los argumentos para invert deben intercambiarse.

Si la orden de evaluación no es determinista , esto no funcionará. El estándar C aparentemente deja este orden no especificado, pero algunos compiladores pueden tener su propio camino. Puede que sepa esto sobre su compilador, pero no es portátil, y su compilador también puede cambiar esto en el futuro. Escribir dicho código está mal visto. Tal vez eso es lo que tus entrevistadores querían saber de ti. Les gustan esos trucos, y quieren ver cómo respondes.

La forma normal de controlar la orden de evaluación es mediante el uso de variables temporales.

Answer 3

Esto es muy simple: recurse al final de la lista, pasando el nuevo puntero next cada vez y devolviendo el final de la lista.

struct list {
    struct list *next;
};

struct list *reverse(struct list *cur, struct list *prev) {
    struct list *next = cur->next;
    cur->next = prev;
    if(next == NULL) return cur;
    return reverse(next, cur);
}

reverse(head, NULL);

Answer 4

Hola chicos, por favor, busquen los programas para la lista de enlaces inversos con y sin recursividad a continuación

LINK *reverse_linked_list_recursion(LINK *head)
{
        LINK *temp;
        if (!head) {
                printf("Empty list/n");
                return head;
        }
        else if (!head->next)
                return head;
        temp = reverse_linked_list_recursion(head->next);
        head->next->next = head;
        head->next = NULL;
        return temp;
}

LINK *reverse_linked_list_without_recursion(LINK *head)
{
        LINK *new, *temp;
        if (!head) {
                printf("No element in the list/n");
                return head;
        }
        else {
                new = head;
                while (head->next) {
                        temp = head->next;
                        head->next = temp->next;
                        temp->next = new;
                        new = temp;
                }
        }
        return new;
}

Answer 5

No sé qué es una "lista de enlaces recursivos", así que iré con su título y supongo que desea "revertir una lista vinculada" utilizando una función recursiva.

Asumiré que se trata de una lista enlazada por separado (de modo que cada elemento tiene un solo puntero al next del siguiente elemento) y por convención tome next = NULL para el último elemento. Para las listas doblemente vinculadas también debe tratar con los punteros prev pero básicamente es la misma idea. Con una lista doblemente vinculada, es más simple ya que ni siquiera necesita hacer un seguimiento del elemento anterior; solo tienes que voltear los dos punteros en cada elemento.

Para invertir la lista, podemos imaginar caminar hacia abajo un elemento a la vez, volteando los next punteros para señalar el elemento anterior a medida que avanzamos. Esto es bastante fácil de escribir como una función recursiva que toma como parámetros un puntero al elemento actual y un puntero al elemento anterior (al comienzo este puntero es NULL ).

node* reverseList(node* head, node* prev = NULL) {
  if (head == NULL) return prev;

  std::swap(head->next, prev); // prev points to next element to process
  return reverseList(prev, head);
}