Ascending sorting of a linked list by node's int value in C

Question

The first approach to linked lists ever. As stated in the title, I'm trying to get a function that sorts a linked list's nodes by their int value (val). But as the function gets called the program leaves me hanging.

Given my simple node struct:

struct node {
    int val;
    struct node* next;
};

This is the function that I hoped would do it:

void sort(struct node** head) {
    struct node* curr = *head;

    while (curr != NULL) {
        struct node* next = curr->next;
        while (next != NULL) {
            if(curr->val > next->val) {
                swap(&curr->val, &next->val);
                // next = next->next; 
            }
            next = next->next; // has to go here
        }
        curr = curr->next;
    }    
}

I acknowledge this might be confusing, but I tried to re-use the same logic as if I had to sort a vector (comparing each item as if I had an index). Thank you in advance for helping me.

EDIT: Just joking, I just noticed that I misconfigured the second while. The next->next node has to go outside the if condition

Answer 1

It makes sense that your code won't work because you're doing bubble sort, which doesn't guarantee the list is sorted by going through a list, array, or ... once.

To bubble sort a linked list you should write it like this:

/* Bubble sort the given linked list */
void sort(node *head)
{
    /* Checking for empty list */
    if (head == NULL) return;

    int swapped;
    node *curr;
    do
    {
        swapped=0;
        curr = head;
        while (curr->next != NULL)
        {
            if (curr->val > curr->next->val)
            {
                int temp = curr->val;
                curr->val = curr->next->val;
                curr->next->val = temp;
                swapped = 1;
            }
            curr = curr->next;
        }
    } while (swapped);
}