ascending sort of a singly linked list

Question

i'm working on this program that sorts a list. but the problem is that the element in head will be ignored in the second recursive call. es:

input: 7->1->8->0->NULL OUTPUT: 1->0->7->8->NULL. 

why is the 1 ignored?

this is the node struct:

struct nodo {
    int elem;
    struct nodo *next;
};

and function:

struct nodo *ordinaLista(struct nodo *head) {
    //in ordine crescente

    if (!head)
        return NULL;
    else {
        if ((head->next) && (head->elem >= head->next->elem)) {
            int tmp = head->elem;
            head->elem = head->next->elem;
            head->next->elem = tmp;
        }
        //printList(head);
        
        head->next = ordinaLista(head->next); 
        head->next = ordinaLista(head->next);
    }
    return head;
}

Answer 1

Your function does not sort the list properly: you only sort the first 2 elements and proceed to sort the rest of the list: the only element guaranteed to end up in the proper position is the greatest one that will become the last element.

Calling the function recursively twice may solve the problem, but you need to change the order of operations: for a simplistic implementation with exponential complexity O(n!), you should first sort the rest of the list, then test if the first element needs swapping with the second element, ensuring that the first element is the smallest one, finally if the elements were swapped, re-sort the rest of the list.

Here is a modified version:

struct nodo *ordinaLista(struct nodo *head) {
    //in ordine crescente

    if (head && head->next) {
        head->next = ordinaLista(head->next); 
        if (head->elem > head->next->elem) {
            int tmp = head->elem;
            head->elem = head->next->elem;
            head->next->elem = tmp;
            head->next = ordinaLista(head->next);
        }
    }
    return head;
}

This approach is very inefficient, but seems to correspond to the code you submitted in the question. Much more efficient approches are available to sort a linked list, such as mergesort.