csortinglinked-listimperative-programming

sort a singly linked list formed of 1, 2 and 0s by swapping the nodes through one traversal in C


I'm trying to solve the question that I need to sort a given linked list which values consist of 1, 2 and 0 by traversing the list only once and I need to swap the nodes not values. my code is:

    #define max 3

void sortList(node **headRef)
{
    if(*headRef==NULL){
        return;
    }
    node* head[max];
    node*tail[max];
    node* curr=*headRef;
    int i;
    for(i=0; i<max; i++){
        head[i]=tail[i]=NULL;
    }
    while(curr!=NULL){
        i=curr->data;
        if(head[i]==NULL){
            head[i]=tail[i]=curr;
        }
        else{
            tail[i]=tail[i]->next=curr;
        }
        curr=curr->next;
    }
    for(int i=0, curr=(*headRef)=NULL; i<max; i++){
        if(head[i]!=NULL){
            if(*headRef==NULL){
                *headRef=head[i];
            }
            else{
                curr = curr->next =head[i];
            }
            curr=tail[i];
        }
        
    }
    curr->next=NULL;
}

but it keep giving me an error and I don't know how to solve it if anyone can help me please.


Solution

  • Your problem is this:

    for(int i=0, curr=(*headRef)=NULL; i<max; i++)
                 ^^^^^^^ here ^^^^^^^
    

    And you solve it by better-understanding the features of the language you're using before you use them. The optional declaration + initialization part of a for-loop allows you to not only initialize, but also declare variables (and in this case, shadow/hide existing variables). The above will declare two loop-scope int variables: i and curr, initializing the first to 0, and the second to the expression result of (*headRef)=NULL, which for near-all C implementations, will be equivalent to (void*)0. But now curr is an int, and the previous declaration of curr as a node pointer is hidden. Therefore, this:

    curr = curr->next =head[i];
    

    is now nonsense.

    Change your code to this:

    curr=(*headRef)=NULL;
    for(int i=0; i<max; i++)
    

    and it should work.