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!

Please [see why not to cast](http://stackoverflow.com/q/605845/2173917) the return value of `malloc()` and family in `C`. — Sourav Ghosh, Jun 25 '15 at 09:31
note that you can not update to the beginning of list by the new node. — BLUEPIXY, Jun 25 '15 at 09:45

chqrlie · Answer 1 · 2015-06-25T11:37:25.880

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.

Also the function does not work because when I try to enter a number to the node it gets two numbers and then it stops again. — Jokerah, Jun 25 '15 at 10:28
a number, for example I enter 1 and then it is suppose to ask me again to enter a number but it doesnt and it lets me enter 2 number for example 1 *I press enter* and then 2, then it crashes. — Jokerah, Jun 25 '15 at 12:42

Sorting a linked list in an ascending way

1 Answers1