Invertir una lista enlazada recursivamente en c

Nuestros mejores desarrolladores han agotado sus reservas de café, investigando día y noche por la solución, hasta que Francisco halló la respuesta en Gitea y en este momento la compartimos aquí.

Solución:

El algoritmo recursivo general para esto es:

1. Divide la lista en 2 partes – primer nodo y resto de la lista.
2. Llamada recursivamente inversa para el rest de la lista enlazada.
3. Enlace rest a first.
4. Arreglar head puntero

Aquí está el código con comentarios en línea:

struct node* recursiveReverseLL(struct node* first)

   if(first == NULL) return NULL; // list does not exist.

   if(first->link == NULL) return first; // list with only one node.

   struct node* rest = recursiveReverseLL(first->link); // recursive call on rest.

   first->link->link = first; // make first; link to the last node in the reversed rest.

   first->link = NULL; // since first is the new last, make its link NULL.

   return rest; // rest now points to the head of the reversed list.

Espero que esta imagen aclare las cosas:

_{(fuente: geeksforgeeks.org)}

.

Solución alternativa:

struct node *head;
void reverse(struct node *prev, struct node *cur)

   if(cur)
      reverse(cur,cur->link);
      cur->link = prev;
    
    else
      head = prev;
    

En main, llama a reverse(NULL,head);

/* Reverses a linked list, returns head of reversed list
*/
NodePtr reverseList(NodePtr curr)  curr->next == NULL) return curr; // empty or single element case

    NodePtr nextElement = curr->next;
    curr->next = NULL;
    NodePtr head = reverseList(nextElement);
    nextElement->next = curr;
    return head;

valoraciones y reseñas

Si estás contento con lo expuesto, puedes dejar un enunciado acerca de qué le añadirías a este ensayo.

---

---

Utiliza Nuestro Buscador