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

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.

CodePudding user response：

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.

CodePudding user response：

Your code is close, but it's a bit cumbersome.

Whenever I see parallel arrays indexed by the same [type of] index, I think of creating a struct. You have head[] and tail[] so I'd create a "bucket" struct.

The multiple assignments in a single line [although doable/legal] makes the code hard(er) to read. Note that:

x = y = z;

Is no faster than:

x = z;
y = z;

if z is a simple scalar. The compiler will generate the same code but the latter is often cleaner/clearer.

Your code may [or may not] handle all cases of lists that are missing one or more of the 0,1,2 values. That is, lists of the form:

0,0,0
1,1,1
2,2,2

0,1
0,2

1,2

Using for loops here is also helps the code readability.

Here's the refactored code (I've compiled it, but not tested it):

#include <stdio.h>

#define max 3

typedef struct node node;
struct node {
    int value;
    node *next;
};

typedef struct {
    node *head;
    node *tail;
} list;

void
sortList(node **headRef)
{
    node *head = *headRef;
    node *tail;
    node *curr;
    node *next;

    if (head == NULL)
        return;

    list *buck;
    list buckets[max] = { 0 };

    // split into buckets
    for (curr = head;  curr != NULL;  curr = next) {
        next = curr->next;
        curr->next = NULL;

        buck = &buckets[curr->value];

        if (buck->head == NULL)
            buck->head = curr;
        else
            buck->tail->next = curr;

        buck->tail = curr;
    }

    // combine buckets into [new] single list
    head = NULL;
    tail = NULL;
    for (int i = 0;  i < max;    i) {
        buck = &buckets[i];

        // skip empty buckets
        if (buck->head == NULL)
            continue;

        // point to _first_ non-empty bucket
        if (head == NULL)
            head = buck->head;

        // append _next_ non-empty bucket
        else
            tail->next = buck->head;

        tail = buck->tail;
    }

    *headRef = head;
}