1

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

Angelo
  • 57
  • 8
  • Is this a homework assignment, or would you be interested in a more efficient sort, such as [bottom up merge sort for linked lists](https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists) ? If so, I can post an answer with working code. – rcgldr May 05 '23 at 22:58
  • @rcgldr It is indeed an exercise given by uni to practice, but I don't have to hand in my code or to follow any specific pattern. So, any alternative way to do this is okay for me! Thanks – Angelo May 06 '23 at 10:08
  • 1
    Link to example of [bottom up merge sort for linked list](https://stackoverflow.com/a/33987943/3282056) . – rcgldr May 06 '23 at 20:39

1 Answers1

4

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);
}