Sortowanie listy przez scalanie.

Jestem nowy na tym forum wiec wszystkich serdecznie witam.
Mam problem z sortowaniem przez scalanie listy jednokierunkowej. Mianowicie nie mam pomysłu jak podzielić listę na dwie. Chciałem przy każdym dzieleniu listy tworzyć dwie nowe listy, ale coś mi nie wychodzi. Szukałem na google, ale znalazłem tylko sortowanie tablic w ten sposób.
Pozdrawiam.

Możesz co drugi element wziąć do pierwszej listy, a resztę do drugiej ;-) Zrobisz to w czasie liniowym względem długości listy. Następnie sortujesz obie listy rekurencyjnie i scalasz je w czasie liniowym. Masz czas O(nlogn)

EDIT: Możesz jeszcze zamienić na tablicę, posortować, zamienić na listę ;->
EDIT2: @down Ten motyw z zamianą na tablicę miał być żartem ;->

No ten pomysł z tablica raczej nie przejdzie. Po to tworze listę żeby odejść od tablicy. Popróbuje jak napisałeś, w razie czego będę pytał.

Raz liczymy dłlugość listy, a później długości podlist przekazujemy w głąb rekursji.
Można też dosyć sprytnie wykonywać podział listy na dwie krótsze(patrz dziel()).
Przy łączeniu nie trzeba drugi raz alokować pamięci.

#include <iostream>
using namespace std;

class lista{
	public:
	int w;
	lista *nast;	
};

lista* dodaj(lista*l, int w){
	lista*t=new lista();
	t->w=w;
	t->nast=l;
	return t;
}

lista* dziel(int n, lista*l){
/* l jest skracane do dlugosci n;
zwracana lista - pozostala czesci listy */	
	lista*t = l;
	n--;
	while(n) {t=t->nast; n--;}
	lista*p = t->nast;
	t->nast = NULL;
	return p;
}

lista* lacz(lista*l, lista*p){
	lista*wynik = NULL, *koniec = NULL, *nast;
	
	while(l != NULL && p != NULL){
		if (l->w <= p->w){
			nast = l->nast;
			if (wynik == NULL){
				wynik = koniec = l;
			} else {
				koniec->nast = l;
				koniec=l;	
			}
			l=nast;	
		} else {
			nast = p->nast;			
			if (wynik == NULL){
				wynik = koniec = p;
			} else {
				koniec->nast = p;
				koniec=p;	
			}	
			p=nast;
		}
	}
	
	if (l != NULL){
		if (wynik == NULL) wynik = l;
		else koniec->nast = l;
	} else{
		if (wynik == NULL) wynik = p;
		else koniec->nast = p;
	}
	return wynik;
}

int dlugosc(lista*l){
	int i=0;
	while(l){
		i++;
		l=l->nast;	
	}		
	return i;
}


lista* sortuj_rek(lista*l, int dl){
	if (dl < 2) return l;
	lista*p=dziel(dl/2,l);
	l=sortuj_rek(l,dl/2);
	p=sortuj_rek(p,dl-dl/2);
	return lacz(l,p);
}
	 	
lista* sortuj(lista*l){
	return sortuj_rek(l, dlugosc(l));
}

void wypisz(lista*l){
	while(l){
		cout << l->w;
		l=l->nast;	
	}	
}

void usun(lista*l){
	while(l){
		lista*t=l;
		l=l->nast;
		delete t;
	}
}

int main(){
	lista *l = NULL;
	l = dodaj(l,5);
	l = dodaj(l,3);
	l = dodaj(l,4);
	l = dodaj(l,5);
	l = dodaj(l,6);
		
	wypisz(sortuj(l));
	usun(l);
	
	return 0;
}

hmm... __krzysiek85 Twoje rozwiązanie na pewno jest dobre, ale ja nie mogę tego zrobić na klasie tylko musi być struktura jak to jest pokazane niżej. Zrobiłem już coś takiego, dziele już listę na połowy, aż dojdzie do listy jednoelementowej, ale nie mogę sobie poradzić z sortowaniem. Jak to zrobić ?

#include <iostream>
#include <cstdlib>
using namespace std;

/////////// Lista jednokierunkowa ///////////
struct wezel{
	int dana;
	wezel *next;
};
struct lista{
	wezel *head;
	wezel *wartownik;
};
/////////////////////////////////////////////

//////////// Deklaracje funkcji /////////////
lista* new_list();
bool empty(lista *l);
void add(lista* l, wezel* w);
wezel* head(lista* l, bool usunac);
int zlicz_wezly(lista* l);
lista* podziel_liste(lista* l);
void wyswietl_liste(lista* l);
void dziel(lista* l);
/////////////////////////////////////////////


int main(int argc, char *argv[])
{
	int licznik;
	bool czy_pusta;
	lista* l=new_list();

	
	for (int i=1; i<=9; i++){ // wproawdzanie danych do listy
	wezel* w = new wezel;
	w->dana = i;
	add(l, w);
	}

	wyswietl_liste(l);	// wyswietlanie listy

	dziel(l);	

	return EXIT_SUCCESS;

}

//////////// Definicje funkcji //////////////
lista* new_list(){
	lista* nl = new lista;
	nl->head = NULL;
	nl->wartownik = NULL;
	return nl;
}

void add(lista* l, wezel* w){
	if (l->head == NULL){
		l->head = w;
		l->wartownik = w;
		l->wartownik->next = NULL;
		}
	else{
		l->wartownik->next = w;
		l->wartownik = w;
		l->wartownik->next = NULL;
		}
}

bool empty(lista *l){
	return l->head==NULL;
}

wezel* head(lista *l, bool usunac=false){
	wezel* tmp = l->head;
	if(usunac){
		l->head = l->head->next;
		}
	return tmp;
}

int zlicz_wezly(lista* l){
	int licznik=0;
	wezel* tmp=l->head;
	while (tmp=tmp->next){
		licznik++;
	}
	return licznik;
}
lista* podziel(lista* l){
	lista* nl_1= new lista;
	lista* nl_2= new lista;
	
}
void wyswietl_liste(lista* l){
	wezel* wsk=l->head;
	while(wsk){
		cout << wsk->dana;
		wsk=wsk->next;
	}
	cout << endl;
}
void dziel(lista* l){
	if(l->head->next){
		lista* l1 = new_list();
		lista* l2 = new_list();
		wezel* wsk = l->head;
		while(wsk){
			wezel* w1 = new wezel;
			w1->dana = wsk->dana;
			add(l1,w1);
			wsk=wsk->next;
			
			if (wsk){
				
				wezel* w2 = new wezel;
				w2->dana = wsk->dana;
				add (l2, w2);
				if(wsk->next==NULL)break;
				wsk=wsk->next;
			}
	
		}
		wyswietl_liste(l1);
		wyswietl_liste(l2);
		dziel(l1);
		dziel(l2); // dzielenie rekurencyjne listy
		
		}
	return;
}
// Zrobic funkcje sortujaca i scalajaca
// Jakies pomysly ?
/////////////////////////////////////////////