[Java] ritorno sbagliato su Merge su ListaConcatenata

[8paolo9]

Ciao a tutti. Ho implementato il mergeSort ricorsivo su una mia lista concatenata e mi sbaglia il ritorno del merge; in poche parole al posto di ritornarmi la lista ordinata, sembra che sovrascriv ogni volta sul primo elemento della lista. La mia lista concatenata è una semplice lista che ha un dato e un puntatore al prossimo elemento. Questo è il mio codice:

public ListaRicorsiva mergeSort () {
	ListaRicorsiva lista1 = new ListaRicorsiva();
	ListaRicorsiva lista2 = new ListaRicorsiva();
	int meta = this.size()/2;
	
	if (meta == 0)
		return this;
	
	else {
		int cont = 1;
		Nodo iterator = first;
		while (cont <= meta) {
			lista1.insertLast(iterator.getDato());
			iterator = iterator.getNext();
			cont++;
		}
		while (cont <= this.size()) {
			lista2.insertLast(iterator.getDato());
			iterator = iterator.getNext();
			cont++;
		}
		return merge (lista1.mergeSort(), lista2.mergeSort());
	}
}
	
	
public ListaRicorsiva merge (ListaRicorsiva lista1, ListaRicorsiva lista2) {
	int cont1 = 0;
	int cont2 = 0;
	ListaRicorsiva listaOrdinata = new ListaRicorsiva();
	Nodo iterator1 = lista1.first;
	Nodo iterator2 = lista2.first;
		
	while (iterator1 != null && iterator2 != null) {
		if (iterator1 != null && iterator2 != null) {
			if(iterator1.getDato() < iterator2.getDato()) {
				listaOrdinata.insertLast(iterator1.getDato());
				iterator1 = iterator1.getNext();
			}
			else {
				listaOrdinata.insertLast(iterator2.getDato());
				iterator2 = iterator2.getNext();
			}
		}
		else if (iterator1 != null && iterator2 == null) {
			listaOrdinata.insertLast(iterator1.getDato());
			iterator1 = iterator1.getNext();	
		}
		else if (iterator2 != null && iterator1 == null) {
			listaOrdinata.insertLast(iterator2.getDato());
			iterator2 = iterator2.getNext();
		}
	}
	return listaOrdinata;
}

Grazie!!

[desa]

Potrei sbagliarmi, ma mi sembra che il problema sia qua:

while (iterator1 != null && iterator2 != null)

Se uno dei due "iterator" (come li hai chiamati) diventa null l'esecuzione viene interrotta anche se l'altro iterator contiene ancora elementi non inseriti in "listaOrdinata"

[8paolo9]

ah ok, allora che condizione dovrei mettere nel while?

[desa]

Per uscire dal while è necessario che entrambi gli "iteratori" siano diventati null (ovverosia che siano stati svuotati dei nodi).
Quindi, il metodo più naturale per gestire tale condizione è

while (iterator1 != null || iterator2 != null)

[8paolo9]

sisi è vero, ora funziona tutto benissimo!! Thanks