Sort a linked-list with only three distinct values 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 &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

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-&gt;data = data;
  temp-&gt;next = NULL;
  if( *head == NULL )
  {
      *head = temp;
      return;
  }
  Node p =(Node)malloc(sizeof(struct node));
  p = *head;
  while( p-&gt;next != NULL )
  {
    p = p-&gt;next;
  }
  p-&gt;next = temp;
}

void display(Node head)
{
  Node p =(Node)malloc(sizeof(struct node));
  p = head;
  while( p != NULL )
  {
    printf("%d ", p-&gt;data);
    p = p-&gt;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-&gt;data == 0 )
    {
      if( temp1 == NULL )
      {
          temp1 = p;
          zero = temp1;
      }
      else
      {
          temp1-&gt;next = p;
          temp1 = temp1-&gt;next;
      }
    }

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

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

    p = p-&gt;next;
  }

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

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




}

int main()
{
  int N;
  scanf("%d", &amp;N);
  Node head = (Node)malloc(sizeof(struct node));
  head = NULL;
  for(int i = 0; i &lt; N; i++)
  {
    int data;
    scanf("%d", &amp;data);
    addnode(&amp;head, data);
  }
  zeroonetwo(&amp;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.
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 &gt;&gt; size;
std::list&lt;int&gt; values;
std::copy_n(std::istream_iterator&lt;int&gt;{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 &lt;&lt; value &lt;&lt; ' ';
std::cout &lt;&lt; '\n';


But I prefer:

std::copy(values.begin(), values.end(), 
          std::ostream_iterator&lt;int&gt;(std::cout, " "));
std::cout &lt;&lt; '\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&lt;int&gt;::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 &lt; 3; ++value)
    for (unsigned int i = 0; i &lt; 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 &lt;map&gt;

template &lt;template &lt;typename ...&gt; typename List, typename ValueType, typename ... Rest&gt;
void splice_sort(List&lt;ValueType, Rest...&gt;&amp; list)
{
    std::map&lt;ValueType, List&lt;ValueType&gt;&gt; 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&amp;&amp; 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 &lt;map&gt;

template &lt;template &lt;typename ...&gt; typename List, typename ValueType, typename ... Rest&gt;
void splice_sort(List&lt;ValueType, Rest...&gt;&amp; list)
{
    std::map&lt;ValueType, List&lt;ValueType&gt;&gt; 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&amp;&amp; locomotive : locomotives)
        list.splice(list.cend(), locomotive.second);
}

#include &lt;list&gt;
using iterator = std::list&lt;int&gt;::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 &lt; 3; ++value)
        for (unsigned int i = 0; i &lt; occurence_count[value]; ++i)
            *start++ = value;
}

#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;iterator&gt;
#include &lt;sstream&gt;

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

    std::copy(values.begin(), values.end(),
              std::ostream_iterator&lt;int&gt;(std::cout, " "));
    std::cout &lt;&lt; '\n';

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

    std::copy(values.begin(), values.end(), std::ostream_iterator&lt;int&gt;(std::cout, " "));
    std::cout &lt;&lt; '\n';
}

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

    std::copy(values.begin(), values.end(),
        std::ostream_iterator&lt;int&gt;(std::cout, " "));
    std::cout &lt;&lt; '\n';

    splice_sort(values);

    std::copy(values.begin(), values.end(), std::ostream_iterator&lt;int&gt;(std::cout, " "));
    std::cout &lt;&lt; '\n';
}

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

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

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


Demo on Wandbox.