Revessar seqüència d'items X86574

Preliminars

En aquest exercici treballarem sobre la següent estructura de dades, que ens serveix per a mantenir una seqüència de valors dins de items encadenats mitjançant punters.

struct Item {
 int value;
 Item* next;
};

Exercici

Implementeu una funció RECURSIVA que, donat un Item* que apunta a una seqüència d’items encadenats, retorna un altre Item* que apunta a una nova seqüència que representa el revessat de la original. En altres paraules, la nova seqüència d’items no comparteix memòria amb la original, però la seva corresponent seqüència de valors és el revessat de la seqüència de valors original.

// Pre:  pitem apunta al primer element d'una seqüència correcta d'items encadenats.
//       L'últim element de la seqüència apunta a NULL. El propi pitem podria ser NULL,
//       cas en el qual no hi hauria elements a la seqüència.
// Post: Retorna un Item* que representa una seqüència d'items nous tals que la seva
//       corresponent seqüència de valors és el revessat de seqüència de valors original.
//       La seqüència original no ha canviat.
Item* reverse(Item* pitem);

Aquí tenim un exemple de paràmetres entrada i sortida de la funció:

reverse([3]->[2]->[5]->[1]->[8]->NULL) = [8]->[1]->[5]->[2]->[3]->NULL

Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: Makefile, program.cpp, reverse.hpp. Us falta crear el fitxer reverse.cpp amb els corresponents includes i implementar-hi la funció anterior. Quan pugeu la vostra solució al jutge, només cal que pugeu un tar construït així:

tar cf solution.tar reverse.cpp

Possiblement necessitareu crear una funció auxiliar amb més paràmetres per tal de resoldre aquest exercici eficientment.

Entrada

L’entrada té un nombre arbitrari de casos. Cada cas consisteix en una línia amb una llista de valors enters. Fixeu-vos en que el programa que us oferim ja s’encarrega de llegir aquestes entrades. Només cal que implementeu la funció abans esmentada.

Sortida

Per a cada cas, la sortida conté dues línies, la primera amb la mateixa llista de valors original, i la segona amb la llista revessada resultant. Fixeu-vos en que el programa que us oferim ja s’encarrega d’escriure aquestes dades. Només cal que implementeu la funció abans esmentada.