Rotació de llistes. X48875

Feu el mètode

void rota (int);

de la classe Llista, la capçalera de la qual és al fitxer llista.hpp.

Quan cridem aquest mètode:

L.rota(n);

on L és una llista de tipus Llista doblement enllaçada, sense fantasma i amb punt d’interès, la llista L es modifica per l’aplicació d’n rotacions a l’esquerra (si $n > 0$) o de $abs(n)$ rotacions a la dreta (si $n < 0$). El punt d’interès no es modifica (segueix apuntant al mateix element que apuntava abans de la rotació). Assumiu que $n \neq 0$.

Podeu imaginar que l’anterior del primer element de la llista és l’últim element, i que el següent element del darrer element de la llista és el primer element (com si fos un cercle), i que moveu el punter al primer element n posicions (tenint en compte la polaritat d’n).

Fixeu-vos que si incrementeu aquest punter imaginari una posició (n = 1), llavors esteu rotant a l’esquerra, i que si el decrementeu una posició (n = -1) esteu rotant a la dreta.

Tingueu en compte que la mida de la llista L serà sempre la mateixa, independentment de les rotacions que se li apliquin.

Podeu assumir que la llista L no és buida (dit altrament: podeu posar a la pre del mètode que el paràmetre implícit té alments un element).

Entrada

El mètode rep un enter $n \neq 0$.

Sortida

El mètode rota la llista del paràmetre implícit $n$ posicions segons la polaritat d’$n$.

Observació

Heu d’enviar la solució comprimida en un fitxer .tar:

tar cvf program.tar rota_llista.cpp

Observeu que per compilar us donem el Makefile, la classe Llista amb tots els seus mètodes implementats (excepte rota) i el programa principal program.cpp.