Sorting a linked list in an ascending way

Question

I am trying to write a function that inserts numbers(from the user)to nodes (1 number for each node) and then sorts them in an ascending way. I wrote this function:

void insertnode(struct n_node *head)
{
    struct n_node *temp = head;
    int number;
    printf("Please insert a number to the node\n");
    scanf("%d", &number);
    while (number != SENTRY)
    {
        while ((temp->next != NULL) && (temp->next->num < number))
        {
            temp = temp->next;
        }
        struct n_node *addNode = (struct n_node*)malloc(sizeof(struct n_node));
        addNode->num = number;
        if (temp->next == NULL && number < temp->num)
        {
            addNode->next = temp;
            head = addNode;
        }
        else
        {
            addNode->next = temp->next;
            temp->next = addNode;
        }
        temp = head;
        scanf("%d", &number);
    }
    options();
}

It compiles but right after I insert the first number is stops, gives me a break message and points on this line:

while ((temp->next != NULL) && (temp->next->num < number))

nothing appears on the error list, any help is appreciated, Thanks!

Answer 1

In your algorithm, you are not testing the special cases in the correct order:

• if the list is empty, head is NULL and the test temp->next != NULL invokes undefined behaviour.
• if the number is smaller than the number in the first node, there is no need to try and iterate over the list, the node needs to be inserted at the head.

You should first allocate the new node and check the special cases with a single test:

 struct n_node *addNode = malloc(sizeof(struct n_node));
 addNode->num = number;

 if (head == NULL || number < head->num) {
     addNode->next = head;
     head = addNode;
 }

Otherwise, your iteration loop is correct and the node is to be inserted after temp when you reach the false condition:

    while (temp->next != NULL && temp->next->num < number) {
        temp = temp->next;
    }
    addNode->next = temp->next;
    temp->next = addNode;

The loop becomes much simpler:

void insertnode(struct n_node **headp) {
    struct n_node *head = *headp;
    int number;
    printf("Please insert a number to the node\n");

    while (scanf("%d", &number) == 1 && number != SENTRY) {
        struct n_node *addNode = malloc(sizeof(struct n_node));
        if (addNode == NULL) {
            printf("out of memory\n");
            return;
        }
        addNode->num = number;

        if (head == NULL || number < head->num) {
            addNode->next = head;
            *headp = head = addNode;
        } else {
            struct n_node *temp = head;
            while (temp->next != NULL && temp->next->num < number) {
                temp = temp->next;
            }
            addNode->next = temp->next;
            temp->next = addNode;
        }
    }
    options(); // head is not passed to the function?
}

Also note the change in API to allow the function to update the list head in the caller's scope, the change to stop scanning for numbers upon end of file or a non number input in addition to a magic number.