Sort a linked-list with only three distinct values

Question

I am trying to solve this problem. The problem is to sort a linked list containing only 0s, 1s and 2s by changing their links.

Sort a linked list of 0s, 1s and 2s by changing links Given a linked list of 0s, 1s and 2s, sort it.

Examples:

Input : 2->1->2->1->1->2->0->1->0 Output : 0->0->1->1->1->1->2->2->2

Input : 2->1->0 Output : 0->1->2

Here is my code:

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

typedef struct node* Node;
struct node
{
  int data;
  struct node* next;
};

void addnode(Node* head, int data)
{
  Node temp = (Node)malloc(sizeof(struct node));
  temp->data = data;
  temp->next = NULL;
  if( *head == NULL )
  {
      *head = temp;
      return;
  }
  Node p =(Node)malloc(sizeof(struct node));
  p = *head;
  while( p->next != NULL )
  {
    p = p->next;
  }
  p->next = temp;
}

void display(Node head)
{
  Node p =(Node)malloc(sizeof(struct node));
  p = head;
  while( p != NULL )
  {
    printf("%d ", p->data);
    p = p->next;

  }
}

void zeroonetwo(Node* head)
{
  if( *head == NULL )
  {
    return;
  }
  Node zero = (Node)malloc(sizeof(struct node));
  Node one = (Node)malloc(sizeof(struct node));
  Node two = (Node)malloc(sizeof(struct node));
  zero = NULL;
  one = NULL;
  two = NULL;
  Node p = (Node)malloc(sizeof(struct node));
  p = *head;

  Node temp1 = (Node)malloc(sizeof(struct node));
  Node temp2 = (Node)malloc(sizeof(struct node));
  Node temp3 = (Node)malloc(sizeof(struct node));
  temp1 = NULL;
  temp2 = NULL;
  temp3 = NULL;


  while( p != NULL  )
  {
    if( p->data == 0 )
    {
      if( temp1 == NULL )
      {
          temp1 = p;
          zero = temp1;
      }
      else
      {
          temp1->next = p;
          temp1 = temp1->next;
      }
    }

    else if( p->data == 1  )
    {
      if( temp2 == NULL )
      {
          temp2 = p;
          one = temp2;
      }
      else
      {
          temp2->next = p;
          temp2 = temp2->next;
      }

    }
    else
    {
        if( temp3 == NULL )
        {
            temp3 = p;
            two = temp3;
        }
        else
        {
            temp3->next = p;
            temp3 = temp3->next;
        }
    }

    p = p->next;
  }

  if( zero != NULL && one != NULL && two != NULL )
  {
    *head = zero;
    temp1->next = one;
    temp2->next = two;
    temp3->next = NULL;

  }
  else if( zero == NULL && one != NULL && two != NULL )
  {
    *head = one;
    temp2->next = two;
    temp3->next = NULL;
  }
  else if( zero == NULL && one == NULL && two != NULL )
  {
    *head = two;
    temp3->next = NULL;
  }
  else if( zero != NULL && one == NULL && two != NULL )
  {
    *head = zero;
    temp1->next = two;
    temp3->next = NULL;
  }
  else if( zero != NULL && one == NULL && two == NULL )
  {
    *head = zero;
    temp1->next = NULL;
  }
  else if( zero == NULL && one != NULL && two == NULL )
  {
    *head = one;
    temp2->next = NULL;
  }
  else
  {
    *head = zero;
    temp1->next = one;
    temp2->next = NULL;
  }




}

int main()
{
  int N;
  scanf("%d", &N);
  Node head = (Node)malloc(sizeof(struct node));
  head = NULL;
  for(int i = 0; i < N; i++)
  {
    int data;
    scanf("%d", &data);
    addnode(&head, data);
  }
  zeroonetwo(&head);
  display(head);
}

But I believe the code can be shortened. The 8 checks to check NULL for zero, one and two seem redundant. I would really appreciate if you someone could provide me suggestions and point any bugs if any exist.

Answer 1

Algorithm

The algorithm linked in the post is a peculiar implementation of counting sort. I'm not sure why splicing and chaining is used, but I believe blunt counting into an array of three elements is much more effective. Your algorithm would be written in generic and comprehensive manner, as ints are always copy constructible.

---

Code

As mentioned in the comments, this is ANSI C. I've actually tried it on ideone and it worked perfectly. I also established that your code works correctly for small inputs (haven't tested others). I'm not sure if reimplementing linked list is part of the task, but I'll suggest you standard library alternatives for the code you've written:

Reading:

Not everybody might agree with me, but I like this usage:

unsigned int size{};
std::cin >> size;
std::list<int> values;
std::copy_n(std::istream_iterator<int>{std::cin}, size, 
            std::back_inserter(values));

As you can see, everything is handled for us. Starting from looping size times, to push_backing items in. It is better to write declarative code that is also efficient. It is not always possible, but this case is easy enough to be handled by declarative code.

printing:

Here is what people usually prefer:

for (int value : values)
    std::cout << value << ' ';
std::cout << '\n';

But I prefer:

std::copy(values.begin(), values.end(), 
          std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';

It is much harder to say which one is more expressive, thus this is more a matter of taste.

sorting:

C++ algorithms on containers are usually written using iterators. Do note though that sometimes iterators get in the way, like when you'll try to implement heap sort (e.g. heavy use of indices is needed). In this case, iterators are pretty good.

Lets start from the signature:

using iterator = std::list<int>::iterator;

void terse_sort(iterator start, iterator end)

Most of the range algorithms are declared like that: start and end of the range. Do note that end is one past the end. Here is an example: if your range is {1, 0, 1, 2}, start will point to leftmost 1, and end will point to "uncertainty" after 2. With that out of the way, lets get to the most interesting part of the algorithm:

counting:

As name of the algorithm implies, use counting:

unsigned int occurence_count[3] = {0};

auto count_pos = start;
while (count_pos != end)
    ++occurence_count[*count_pos++];

Thw while loop is the same as (p != NULL) in the code. For every index 0, 1, 2, occurence_count will tell how many of those occured in the list. Now, lets put the values in the correct places:

for (unsigned int value = 0; value < 3; ++value)
    for (unsigned int i = 0; i < occurence_count[value]; ++i)
        *start++ = value;

As it can be observed, for index 0, it is gonna write 0 from the start, occurence_count[0] times. The same for indices 1 and 2.

---

The algorithm mentioned in the linked post

I actually thought about it a little. The thing is that it doesn't perform any swaps! So, if blunt counting sort performs copies (e.g. doesn't regard cases where key!=value), the mentioned algorithm preserves relative order and regards keys not being the same as value. I found it really peculiar, thus decided to implement somewhat more generic version:

#include <map>

template <template <typename ...> typename List, typename ValueType, typename ... Rest>
void splice_sort(List<ValueType, Rest...>& list)
{
    std::map<ValueType, List<ValueType>> locomotives;
    while (list.size() != 0)
    {
        auto locomotive_end = locomotives[list.front()].cend();
        locomotives[list.front()].splice(locomotive_end, list, list.begin());
    }

    //no elements left in list,
    //put it back in the correct order
    for (auto&& locomotive : locomotives)
        list.splice(list.cend(), locomotive.second);
}

Since the algorithm is designed for types that are heavy to swap, they are probably not ints, but std::arrays or some other weird swappable type.

---

A bit of trivia.

Why locomotive?

By Marcus Wong Wongm [GFDL (http://www.gnu.org/copyleft/fdl.html) or CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0)], from Wikimedia Commons

In countries of post-Soviet era, the trains led by locomotives are commonplace, especially just after the collapse of Soviet union. When reading about the algorithm, I recalled my travels on those when I was a kid. The algorithms behaves like merge of trains: trains with lower value are appended to ones which have next bigger value, and so on until all trains are merged into one. Also the splice sort preserves relative order and regards keys not being values, like people in wagons are not their priorities, and vice versa.

---

Full code to play with

#include <map>

template <template <typename ...> typename List, typename ValueType, typename ... Rest>
void splice_sort(List<ValueType, Rest...>& list)
{
    std::map<ValueType, List<ValueType>> locomotives;
    while (list.size() != 0)
    {
        auto locomotive_end = locomotives[list.front()].cend();
        locomotives[list.front()].splice(locomotive_end, list, list.begin());
    }

    //no elements left in list,
    //put it back in the correct order
    for (auto&& locomotive : locomotives)
        list.splice(list.cend(), locomotive.second);
}

#include <list>
using iterator = std::list<int>::iterator;

void terse_sort(iterator start, iterator end)
{
    unsigned int occurence_count[3] = { 0 };

    auto count_pos = start;
    while (count_pos != end)
        ++occurence_count[*count_pos++];


    for (unsigned int value = 0; value < 3; ++value)
        for (unsigned int i = 0; i < occurence_count[value]; ++i)
            *start++ = value;
}

#include <iostream>
#include <algorithm>
#include <iterator>
#include <sstream>

void terse_sort_demo(std::istream& in)
{
    unsigned int size{};
    in >> size;
    std::list<int> values;
    std::copy_n(std::istream_iterator<int>{in}, size, std::back_inserter(values));

    std::copy(values.begin(), values.end(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';

    terse_sort(values.begin(), values.end());

    std::copy(values.begin(), values.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

void splice_sort_demo(std::istream& in)
{
    unsigned int size{};
    in >> size;
    std::list<int> values;
    std::copy_n(std::istream_iterator<int>{in}, size, std::back_inserter(values));

    std::copy(values.begin(), values.end(),
        std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';

    splice_sort(values);

    std::copy(values.begin(), values.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

int main()
{
    const std::string input = "6\n"
        "2 0 0 2 1 1\n";
    std::istringstream input_stream(input);

    std::cout << "splice sort:\n";
    splice_sort_demo(input_stream);
    std::cout << "\n\n";

    input_stream.str(input);
    std::cout << "raw counting sort:\n";
    terse_sort_demo(input_stream);
}

Demo on Wandbox.

Answer 2

Don't label your code C and C++

These are two distinct languages and advice in one language may not be the same as the other language. I like C++ so my advice is fro writing C++. Which will generally be wrong for writing C code.

typedef is not needed here

typedef struct node* Node;
struct node
{
  int data;
  struct node* next;
};

In C Node should probably be called NodeP as its a pointer type. It makes it nice to declare the Node as an object type. In C++ this trick is no longer needed as structures are not in their own namespace (like in C).

// C++ you can simply declare this.
struct Node
{
  int   data;
  Node* next;
};

But I will use struct node in the rest of my code review.

Only going to look at the sorting algorithm:

void zeroonetwo(Node* head)
{
  if( *head == NULL )
  {
    return;
  }
  Node zero = (Node)malloc(sizeof(struct node));
  Node one = (Node)malloc(sizeof(struct node));
  Node two = (Node)malloc(sizeof(struct node));
  zero = NULL;
  one = NULL;
  two = NULL;
  Node p = (Node)malloc(sizeof(struct node));
  p = *head;

  Node temp1 = (Node)malloc(sizeof(struct node));
  Node temp2 = (Node)malloc(sizeof(struct node));
  Node temp3 = (Node)malloc(sizeof(struct node));
  temp1 = NULL;
  temp2 = NULL;
  temp3 = NULL;


  while( p != NULL  )
  {
    if( p->data == 0 )
    {
      if( temp1 == NULL )
      {
          temp1 = p;
          zero = temp1;
      }
      else
      {
          temp1->next = p;
          temp1 = temp1->next;
      }
    }

    else if( p->data == 1  )
    {
      if( temp2 == NULL )
      {
          temp2 = p;
          one = temp2;
      }
      else
      {
          temp2->next = p;
          temp2 = temp2->next;
      }

    }
    else
    {
        if( temp3 == NULL )
        {
            temp3 = p;
            two = temp3;
        }
        else
        {
            temp3->next = p;
            temp3 = temp3->next;
        }
    }

    p = p->next;
  }

  if( zero != NULL && one != NULL && two != NULL )
  {
    *head = zero;
    temp1->next = one;
    temp2->next = two;
    temp3->next = NULL;

  }
  else if( zero == NULL && one != NULL && two != NULL )
  {
    *head = one;
    temp2->next = two;
    temp3->next = NULL;
  }
  else if( zero == NULL && one == NULL && two != NULL )
  {
    *head = two;
    temp3->next = NULL;
  }
  else if( zero != NULL && one == NULL && two != NULL )
  {
    *head = zero;
    temp1->next = two;
    temp3->next = NULL;
  }
  else if( zero != NULL && one == NULL && two == NULL )
  {
    *head = zero;
    temp1->next = NULL;
  }
  else if( zero == NULL && one != NULL && two == NULL )
  {
    *head = one;
    temp2->next = NULL;
  }
  else
  {
    *head = zero;
    temp1->next = one;
    temp2->next = NULL;
  }




}

int main()
{
  int N;
  scanf("%d", &N);
  Node head = (Node)malloc(sizeof(struct node));
  head = NULL;
  for(int i = 0; i < N; i++)
  {
    int data;
    scanf("%d", &data);
    addnode(&head, data);
  }
  zeroonetwo(&head);
  display(head);
}

Which though nearly unreadable looks like it might actually work (after lots of parsing).

Don't allocate and leak

  Node zero = (Node)malloc(sizeof(struct node));
  zero = NULL;  // You just leaked the allocated memory.

  // There is no need to allocate memory here at all.
  // Simply do:
  Node zero = nullptr;  // In C++ we use nullptr not NULL

Consistency in naming

Node zero  = nullptr; // Why does this start from zero
Node one   = nullptr;
Node two   = nullptr;

Node temp1 = nullptr; // When this one starts from 1!
Node temp2 = nullptr;
Node temp3 = nullptr;

if( p->data == 0 )       // Talking about number zero
{
    if( temp1 == NULL )  // but using variable one!!

Name variables in a way that is useful and makes reading the code easy

Its not obvious but zero/one/two represent the head of a list and temp1/tempt2/temp3 represent the tail of a list. So use a good nameing scheme that makes that a bit more explicit.

Node head0 = nullptr;
Node head1 = nullptr;
Node head2 = nullptr;

Node tail0 = nullptr;
Node tail1 = nullptr;
Node tail2 = nullptr;

Use arrays to remove repetition.

  while( p != NULL  )
  {
    if( p->data == 0 )
    {
      if( tail0 == NULL )
      {
          tail0 = p;
          head0 = temp1;
      }
      else
      {
          tail0->next = p;
          tail0 = tail0->next;
      }
    }
    else if( p->data == 1  )
    {
        // Use same code as in data == 0 but 
        // replace tail0(temp1) with tail1(temp2) and head0(zero) with head1(one)
    }
    else
    {
        // Use same code as in data == 0 but
        // replace tail0(temp1) with tail2(temp3) and head0(zero) with head2(two)
    }

Rather than just use an array indexed by p->data

  Node head[3] = {0};
  Node tail[3] = {0};
  while( p != NULL  )
  {
      if( head[p->data] == NULL )
      {
          head[p->data] = p;
          tail[p->data] = p;
      }
      else
      {
          tail[p->data]->next = p;
          tail[p->data]       = p;
      }
    }

Think about using a Sentinel and tail (rather than head and tail).

Sentinels are fake values in a list (or chain). They make it much easier to deal with NULL values (as there never is an empty list).

  struct node head[3] = {0}; // Note Values not pointers.
  Node        tail[3] = {&head[0], &head[1], &head[2]};
  while( p != NULL  )
  {
      tail[p->data]->next = p;
      tail[p->data]       = p;
  }

You can simplify the building of the arrays

    Node  working = nullptr;
    Node  end     = nullptr;

    for(int loop = 0;loop < 3;++loop) {
        if (end) {
            end->next = head[loop].next;
        }

        working = working ? working : head[loop].next;
        if (working) {
            end = tail[loop];
        }
    }

Final Code

struct Node
{
    int value;
    Node* next;
};

Node* sort123(Node* list)
{
    Node    head[3]   = {0};
    Node*   tail[3]   = {&head[0], &head[1], &head[2]};

    for(;list != nullptr; list = list->next) {
        tail[list->value]->next = list;
        tail[list->value]       = list;
    }

    Node* working = nullptr;
    Node* end     = nullptr;
    Node* last    = nullptr;
    for(int loop = 0;loop < 3;++loop) {
        if (end) {
            end->next = head[loop].next;
        }

        working = working ? working : head[loop].next;
        if (working) {
            end = tail[loop];
        }

        last = head[loop]->next ? tail[loop] : last;
    }
    if (last) {
        last->next = nullptr;
    }
    return working;
}

Answer 3

Avoid typedefs

Typedefs should be used rarely; you do not gain very much by them but they obfuscate code (you do not see whether it is a cheap basic type, a large object, or a pointer). So, remove the

typedef struct node* Node;

Rethink the list implementation

Although

struct node
{
  int data;
  struct node* next;
};

is a classic implementation of a single linked list which can be found in many text books, there exist better ways to declare such a list:

struct slist_head {
    struct slist_head *next;
}

struct node {
    int data;
    struct slist_head head;
};

This allows to implement generic slist operations (add, delete, splice) instead of writing them for every kind of object which uses an slist.

I will use later a container_of macro which is implemented like

#define container_of(_ptr, _type, _attr) \
    ((_type *)((uintptr_t)(_ptr) - offsetof(_type,_attr)))

to cast slist_head to the containing node.

Split the list operations

void addnode(Node* head, int data)
{
    Node temp = (Node)malloc(sizeof(struct node));

should be splitted into two parts:

1. creation of the object
2. appending the data to the list

E.g. when you "node" contains more than a simple int (the problem linked by you speaks about objects containing colors), your function needs more and more parameters.

I would write this like

void slist_add(struct slist_head *head, struct slist_head *root)
{
    head->next = root->next;
    root->next = head;
}

and later in main()

struct slist_head root = { .next = NULL };
...
    struct node *node = malloc(sizeof *node);
    scanf("%d", &node->data);
    slist_add(&node->head, &root);

Later, we need a function to add a list to another one:

struct slist_head **slist_end_ptr(struct slist_head *list)
{
    struct slist_head **ptr = &list->next;

    while (*ptr)
        ptr = &((*ptr)->next);

    return ptr;
}

void slist_splice_tail(struct slist_head *list, struct slist_head *root)
{
    struct slist_head **end = slist_end_ptr(root);

    *end = list->next;
    list->next = NULL;
}

Sorting

Because you know, that only numeric 0, 1 and 2 values are possible, you can write this as

struct slist_head tmp_roots[] = {
    [0] = { .next = NULL },
    [1] = { .next = NULL },
    [2] = { .next = NULL },
};

struct slist_head *pos = root->next;

while (pos != NULL) {
    struct slist_head *next = pos->next;
    struct node *node = container_of(pos, struct slist_head, head);

    /* we remove 'pos' from 'root' in the next step, but because 'delete' 
       operations on single linked lists are expensive and we know what 
       we are doing, skip the cleanup here and do it farther below */

    slist_add(pos, &tmp_roots[node->data]);

    pos = next;
}

/* we moved all members of `root` into other lists; empty it here */
root->next = NULL;

Of curse, for real code, you should add sanity checks before accessing tmp_roots[node->data]. When more than the three values are possible, you can/should allocate and initialize tmp_roots dynamically.

Finally you can concatenate the tmp_roots:

for (size_t i = 0; i < 3; ++i)
    slist_splice_tail(&tmp_roots[i], &root);

The whole program

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

struct slist_head {
    struct slist_head *next;
};

struct node {
    int data;
    struct slist_head head;
};

#define container_of(_ptr, _type, _attr)            \
        ((_type *)((uintptr_t)(_ptr) - offsetof(_type,_attr)))

static void slist_add(struct slist_head *head, struct slist_head *root)
{
    head->next = root->next;
    root->next = head;
}

static struct slist_head **slist_end_ptr(struct slist_head *list)
{
    struct slist_head **ptr = &list->next;

    while (*ptr)
        ptr = &((*ptr)->next);

    return ptr;
}

static void slist_splice_tail(struct slist_head *list, struct slist_head *root)
{
    struct slist_head **end = slist_end_ptr(root);

    *end = list->next;
    list->next = NULL;
}

static void sort_012_list(struct slist_head *root)
{
    struct slist_head tmp_roots[] = {
        [0] = { .next = NULL },
        [1] = { .next = NULL },
        [2] = { .next = NULL },
    };

    struct slist_head *pos = root->next;

    while (pos != NULL) {
        struct slist_head *next = pos->next;
        struct node *node = container_of(pos, struct node, head);

        slist_add(pos, &tmp_roots[node->data]);

        pos = next;
    }

    root->next = NULL;

    for (size_t i = 0; i < 3; ++i)
        slist_splice_tail(&tmp_roots[i], root);
}

int main(void)
{
    struct slist_head    root = { .next = NULL };
    int N;

    scanf("%d", &N);    
    for(int i = 0; i < N; i++) {
        struct node *node = malloc(sizeof *node);
        scanf("%d", &node->data);
        slist_add(&node->head, &root);
    }

    sort_012_list(&root);

    printf("result:");
    for (struct slist_head *i = root.next; i != NULL; i = i->next) {
        struct node *node = container_of(i, struct node, head);

        printf(" %d", node->data);
    }
    printf("\n");
}