[Java] problema inversione lista....

[ViRUZ_gTi]

ciao a tutti sono nuovo del forum ho un problema con le liste
dunque mi occorre un metodo ricorsivo che mi modifichi la lista invertendola "sul posto"
vi posto le classi nodo e lista ed un metodo ricorsivo che mi stampa la lista (assunta ordinata) senza ripetizioni
ho usato due metodi uno nella classe nodo che mi escludeva i nodi ripetuti
e un metodo nella classe lista per modificarla, mi occorrerebbe fare qualcosa del genere anche per invertirla ma non ci riesco proprio

n.b. mi è stato chiesto il non utilizzo di iteratori, solo metodi ricorsivi
vi ringrazio tutti in anticipo

ecco le classi di cui dispongo
questa è la classe nodo:

//modifica la lista senza ripetizioni (assumendo lista ordinata)

public class Nodo{
   Object elemento;
   Nodo next;
   public Nodo(Object elemento,Nodo next) {
      this.elemento=elemento;
      this.next=next;
   }
   public Nodo (Object elemento) {
      this.elemento=elemento;
      this.next=null;
   }
   public Nodo copia(){
       Nodo nuovo = new Nodo(elemento,next);
       if (next==null) return nuovo;
       else if ( !(this.elemento).equals(this.next.elemento) ){
           nuovo.next=next.copia();
           return nuovo;
       }
       else return next.copia();
   }
}

questa è la classe lista:

//modifica la lista senza ripetizioni (assumendo lista ordinata)

public class Lista{
   private Nodo header;
   private int size;  
   public Lista(){
        size=0;
   }
    public void modificaLista(){
       if(size!=0) header=header.copia();
       else header=null;
   }
}

[ViRUZ_gTi]

ragazzi nessuno mi dà una mano tra poco ho l'esame sono disperato

[andbin]

Se devi invertire una lista, la prima cosa che salta all'occhio è che dovrai modificare solamente i 'next' dei nodi in modo che un nodo non punti più al successivo ma al precedente.

La questione della ricorsione complica solo di poco le cose, per lo meno concettualmente. Se lo si fa bene e in modo logico, bastano poche righe di codice.

Una soluzione è fare un metodo ricorsivo che ha come parametro 2 nodi: quello "attuale" e quello "precedente". Il metodo dovrà fare in modo che il nodo punti al precedente (e questo è facile) ma dovrà anche fare la ricorsione.

La parte più importante è che una volta invertita la lista, il nuovo "head" sarà l'ultimo nodo della lista iniziale. Questo vuol dire che la ricorsione deve proseguire in avanti e arrivato all'ultimo nodo deve iniziare il processo inverso, cioè ritornare indietro facendo ritornare come valore sempre quell'ultimo nodo.

[ViRUZ_gTi]

dunque rigrazio andrea per le delucidazioni
ho fatto come hai detto però sbaglio ancora qualcosa ti mostro il codice...

public class Lista{
   private Nodo header;
   private int size;
   public Lista(){
        size=0;
   }
   //metodo aggiunge un elemento in testa
   public void add(Object o) {
        if (size==0) {
            header = new Nodo(o);
        }
        else {
            Nodo nuovoNodo = new Nodo(o,header);
            header = nuovoNodo;
        }
        size++;
   }
   //metodo stampa header
   public void print(){
       if(size!=0) header.print();
       else System.out.println("Lista vuota");
   }
   //inverti lista
   public void invertiLista(){
       if(size==0) header=null;
       else if(size==1) header=header;
       else header=header.inverti(header.next,header);
   }
}

public class Nodo{
   Object elemento;
   Nodo next;
   public Nodo(Object elemento,Nodo next) {
      this.elemento=elemento;
      this.next=next;
   }
   public Nodo (Object elemento) {
      this.elemento=elemento;
      this.next=null;
   }
   public void print() {
	  System.out.println(elemento);
	  if (next!=null) next.print();
   }
   public Nodo inverti(Nodo attuale, Nodo precedente){
       //se arrivo all'ultimo nodo della lista
       if(attuale.next==null){
           if(precedente!=null) {
           //restituisco un nodo che punta al nodo precedente
           Nodo nuovo = new Nodo(attuale.elemento,precedente);
           //ricorsivamente fino a quando il nodo precedente non è nullo
           return nuovo.inverti(nuovo, attuale);
           }
           else return new Nodo(attuale.elemento);
       }
       //effettuo una ricorsione finchè non arrivo all'ultimo nodo
       else return next.inverti(attuale,precedente);    
   }
}

metto anche la classe Test (main) che ho creato per fare le verifiche...

import java.io.*;

public class Test {

   public static void main (String[] args) throws IOException {
       
   Lista list = new Lista();
   BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
   
   System.out.println("quanti elementi vuoi aggiungere alla lista list?");
   int a = Integer.parseInt(buffer.readLine());
   
     for (int i=0; i<a; i++){
       System.out.println("inserisci un elemento in testa a list1: ");
       list.add( Integer.parseInt(buffer.readLine()) );
     }

   
   System.out.println("\nstampo gli elementi della lista list.....");
   list.print();
   System.out.println("\ninversione sul posto.....");
   list.invertiLista();
   System.out.println("\nstampo gli elementi della lista invertita.....");
   list.print();
   }
}

dunque il metodo modificaLista() dovrebbe invertire la lista richiamando il metodo ricorsivo della classe nodo che accetta i due parametri Nodo attuale e Nodo precedente
nella classe lista poi non sò cosa inserire come attuale ho inserito header.next e come precedente header non sò se và bene
così come ho postato mi manda un'eccezione di tipo NullPointerException non appena gli elementi della lista sono >1 (non effettua il metodo per size==0 e size==1 classe lista)

help me please!!!

[andbin]

Originariamente inviato da ViRUZ_gTi

   public Nodo inverti(Nodo attuale, Nodo precedente){
       //se arrivo all'ultimo nodo della lista
       if(attuale.next==null){
           if(precedente!=null) {
           //restituisco un nodo che punta al nodo precedente
           Nodo nuovo = new Nodo(attuale.elemento,precedente);
           //ricorsivamente fino a quando il nodo precedente non è nullo
           return nuovo.inverti(nuovo, attuale);
           }
           else return new Nodo(attuale.elemento);
       }
       //effettuo una ricorsione finchè non arrivo all'ultimo nodo
       else return next.inverti(attuale,precedente);    
   }

Troppo lungo ( io l'ho fatto con 3 righe di codice, senza alcun if e solo 1 operatore ternario ?: ).
Ma a parte la lunghezza, non vedo perché devi istanziare dei nuovi nodi. C'è solo da modificare il 'next' dei nodi e basta.

[ViRUZ_gTi]

si lo sò che non è efficientissimo speravo almeno funzionasse
cmq è lungo anche per il commenti

non è che potresti mostrarmi il tuo metodo ti giuro sò che è una cosa banalissima però ci sto sbattendo la testa da due giorni e tra poco ho l'esame di algoritmi e strutture dati
grazie

[andbin]

Io farei:

public Nodo inversione (Nodo prev, Nodo n)
{
    Nodo next_t = n.next;

    n.next = prev;

    return next_t != null ? inversione (n, next_t) : n;
}

Da invocare con:

head = inversione (null, head);

L'unico caso particolare è che non deve essere invocato se 'head' è null (=nessun nodo) ma si tratta solo di mettere prima un test.

[ViRUZ_gTi]

fantastico!
grazie andrea sei stato gentilissimo veramente mi hai risolto un bel problema