Sorting singly linked list with minimum time complexity

[kayl]

Hello all ...

please could anyone help with writing a method to sort singly linked list with minimum time complexity ...

plz it will be glad if u post me the code ....


Thanks.

[jackji]

You can create table of pointers to your list elements and then use qsort:

int n = //no. of elements in linked list
list_elem* first_elem = //first element of linked list

list_elem **tab, *it;
int i;
tab = new (list_elem*)[n];

for(it = first_elem, i=0; i<n; i++, it = it->next)
tab[i] = it;

qsort(tab, n, sizeof(list_elem*), compare_func);

and implement compare_func like that:

int compare_func(const void* e1, const void* e2) {
const list_elem* elem1 = *(list_elem**)e1;
const list_elem* elem2 = *(list_elem**)e2;

//here add code coparing elem1 and elem2
//return <0 it elem1 goes before elem2, 0 if equal, >0 if goes after
}