Sorting a linked list in ascending order in C

Question

I am working on a program for my C programming course that is supposed to give us experience using linked lists. One of the last parts of the assignment asks for us to take a linked list and sort it in ascending order using prepend or append functions that we wrote earlier in our program.

struct lnode
{
  int datum;
  struct lnode *next;
};


struct lnode*
prepend(struct lnode *list, int x)
{
  struct lnode *node = (struct lnode *)malloc(sizeof(struct lnode));
  node -> datum = x;
  node -> next = list;
  list = node;
  return list;
}

struct lnode*
append(struct lnode *list, int x)
{
  if(list==NULL){
    list = (struct lnode *)malloc(sizeof(struct lnode));
    list -> datum = x;
    list -> next = NULL;
  }else{
    list -> next = append(list->next,x);li
  }
  return list;
}

Above are both the append and prepend functions which we designed in our class.

Below is the delete fuction, something we also made in class:

struct lnode*
delete(struct lnode *list, int x)
{
  struct lnode* tmp;
  if(list == NULL){
    return list;
  }else if(list-> datum == x){
    tmp = list -> next;
    list -> next = NULL;
    free(list);
    list = tmp;
    return list;
  }else{
    list->next = delete(list->next,x);
    return list;
  }
}

int
find_smallest(struct lnode*list)
{
  int smallest;
  smallest = list->datum;
  while(list!=NULL){
    if(list->datum < smallest){
      smallest = list->datum;
    }
    list = list->next;
  }
  return smallest;
}

The function find_smallest takes a linked list as its input and should return the smallest integer value in the linked lists. I've tested this function multiple times and it seems to be working perfectly.

Finally, sort, which is below, should create a new linked list new_list and should append the value of the smallest integer in list and then delete that value from list until list no longer has any values.

struct lnode*
sort(struct lnode *list)
{
  struct lnode *new_list;
  while(list != NULL && list->next != NULL){
    new_list = append(new_list, find_smallest(list));
    list = delete(list, find_smallest(list));
  }
  return new_list;
}

The issue that I'm having is that it appears I am getting an infinite loop. I ran a test case where I printed the elements of list after each running of the loop where list was originally 5 4 1 2 3 and what printed out was 5 4 2 3 over and over again until I forced the program to stop. So I believe it's only running correctly once?

Answer 1

The variable new_list is not initialized in the sort function. The append function then incorrectly appends to a non-existant node.

Change

struct lnode *new_list;

to

struct lnode *new_list = NULL;

in the sort function.