[C++] Invertire i nodi di una lista in modo ricorsivo

[Squall1988]

Ho un simpatico problema: sto cercando disperatamente di invertire l'ordine dei nodi di una lista semplicemente concatenata, però non nel modo classico iterativo, bensì ricorsivo... Ci sto provando da un po' ma mi pare abbastanza infattibile.
Cosa ne pensate???

(3->5->9->2 deve diventare 3<-5<-9<-2)

[oregon]

Con quale codice ci stai provando ?

[Squall1988]

ah come codice sinceramente non riesco neanche a capire dove partire, è per quello che ho chiesto aiuto, anche come pensare ricorsivamente l'algoritmo mi pare quasi impossibile.

[unomichisiada]

Originariamente inviato da Squall1988
ah come codice sinceramente non riesco neanche a capire dove partire, è per quello che ho chiesto aiuto, anche come pensare ricorsivamente l'algoritmo mi pare quasi impossibile.

L'ultimo deve diventare il primo o cosa? Beh magari non è semplice ma impossibile forse è esagerato.

[Squall1988]

infatti ho detto quasi
comunque si, deve risultare invertita, ma non cambiando i dati ma i puntatori ai nodi successivi.

[unomichisiada]

Non era poi così difficile!!Il codice sensibile è nella funzione FlipList, il resto è brodo.

#include <stdio.h>
#include <stdlib.h>

struct Node
{
	int el;
   struct Node *next;
};

typedef struct Node Node;
void * myalloc(int n);
Node *ListCreate(Node *head,int el);   //inserisce in coda
Node* FlipList(Node *head,Node* prev);
void PrintList(Node *head);
int main()
{
   Node *head = NULL;
	int v[10]={8,-5,-7,2,0,6,33,5,-45,-12},i,n=10;
	for(i=0;i<n;i++)
	{
		head=ListCreate(head,v[i]);
	}

   printf("\n\nLista : ");
   PrintList(head);
   printf("\n\nLista invertita: ");
   head = FlipList(head,NULL);
   PrintList(head);
	fflush(stdin);
   getchar();
   return 0;
}

void * myalloc(int n)
{
	void * p=malloc(n);
   if(!p)
   {
   	printf("Memoria insufficiente!!");
      exit(1);
      fflush(stdin);
   	getchar();
   }
   return p;
}

Node *ListCreate(Node *head,int el)
{
	//inserisce in coda
	Node * p=(Node*)myalloc(sizeof(Node)),*t;
   p->el=el;
   p->next=NULL;
   t=head;
   if(!t)	return p;
   while(t->next) 	t=t->next;
   t->next=p;
   return head;
}

void PrintList(Node *head)
{
	while(head)
   {
   	printf("%d ",head->el);
   	head=head->next;
   }
}

//Come vedi non era impossibile!!!
Node* FlipList(Node *head,Node* prev)
{
	Node *p;
	if(!head)
	{
		return prev;
	}
	p = FlipList(head->next,head);
	head->next = prev;
	return p;
}

[unomichisiada]

Mi sono accorto che avevi messo C++ nel titolo e che io ti ho dato una soluzione in c, scusa ma dalla richiesta ho dato invece per scontato il c. Comunque convertirlo è abbstanza semplice...

[Squall1988]

no cioè, sei un genio grazie mille