Sorting a linked list in C

Question

I'm trying to sort a linked list by finding the largest value, deleting it from its position, and then inserting it at the top of the list.

The difficulty I'm running into is the actual deleting and inserting at the top. The issue seems to be in the if condition in the while loop contained within the sortList function, but I'm not sure how to fix it.

Any help would be appreciated.

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int num;
    struct node *next;
} Node, *NodePtr;

void printList(NodePtr np);
NodePtr makeList(void);
NodePtr makeNode(int n);
NodePtr sortList(NodePtr list);

int main(void) {
    NodePtr list;
    printf("Enter numbers for the list (0 to end)\n");
    list = makeList();
    printList(list);
    list = sortList(list);
    printList(list);
    return 0;
}

NodePtr makeList(void) {
    NodePtr makeNode(int), np, top, last;
    int n;
    top = NULL;
    if(scanf("%d", &n) != 1)n = 0;
    while(n != 0) {
        np = makeNode(n);
        if(top == NULL)top = np;
        else last->next = np;
        last = np;
        if(scanf("%d", &n)!=1)n=0;
    }
    return top;
}


void printList(NodePtr np) {
    while(np != NULL) {
        printf("%d\n", np->num);
        np = np->next;
    }
}

NodePtr makeNode(int n) {
    NodePtr np = (NodePtr)malloc(sizeof(Node));
    np->num = n;
    np->next = NULL;
    return np;
}

NodePtr sortList(NodePtr list) {
    NodePtr top = list;
    NodePtr curr = NULL;
    NodePtr largest;
    NodePtr prev;
    prev = NULL;
    curr = top;
    largest = top;

    while(curr != NULL) {
        prev = curr;
        if(curr->num > largest->num) {
            largest = curr;
            prev->next = curr->next;
            largest->next = top;
        }
        curr = curr->next;
    }
    if(prev == NULL) {
        largest->next = top;
        return largest;
    }
    return largest;
}

Answer 1

There is issues in the sortList function.

This function only put some large nodes in the beginning of the list. It is not soting all the list. you can you a sort algorithm to sort the file : quicksort/ bubblesort/... i put a code doing a sort in the end of this answer.

here is a code doing the sort of the list :

//it is replacing largest node with first one then doing the same operation with sublist (list-first element)

NodePtr sortList(NodePtr list) 
{

// 
if(list == null || list->next == null)
    return list; // the list is sorted.

//replace largest node with the first : 

//1- find largest node : 
NodePtr curr, largest,largestPrev;
curr = list;
largest = list;
prev = list;
largestPrev = list;
while(curr != NULL) {
        if(curr->num > largest->num) {
            largestPrev = prev;
            largest = curr;
        }
        prev = curr;
        curr = curr->next;

    }
//largest node is in largest. 

//2- switching firt node and largest node : 
NodePtr tmp;
if(largest != list)
{
    largestPrev->next = list;
    tmp = list->next;
    list->next = largest->next;
    largest->next = tmp;
}

// now largest is the first node of the list.

// calling the function again with the sub list :
//            list minus its first node :
largest->next = sortList(largest->next);


return largest;
}