Sorting a linked list of 0s, 1s and 2s

Given a Singly linked list with each node containing either 0, 1 or 2. Write code to sort the list.

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

Solution:

Usually Merge Sort can used to sort a Random linked list. But since this is special list, we can do the sorting in linear time. Below are the two methods, both linear time (O(n)-Time) which can be used to sort.

1. Counting occurrences.

1.Count the occurences of o's 1's and 2's in the list.
    (let ct0, ct1, ct2 represent the number of 0's, 1's and 2's in the list respectively)
2.traverse the list and
  - set first ct0 Nodes to 0
  - set next ct1 Nodes to 1
  - set first ct2 Nodes to 2

Code:

/**
 * Sorts a Special list where each Node is either 0, 1 or 2.
 * Will bring all the zeros toward the head, All 2's toward the tail
 * and leave all the 1's as it is.
 *
 * head passed by value, because nodes are not changing. Just copying data to the Node.
 */
void sortUsingcounting(Node* head)
{
    if(head == NULL || head->link == NULL)
        return;
    int count0 = 0;
    int count1 = 0;
    int count2 = 0;
    // Counting the occurences
    for(Node* temp=head; temp!=NULL; temp=temp->link)
    {
        switch(temp->data)
        {
        case 0:
            count0++; break;
        case 1:
            count1++; break;
        case 2:
            count2++; break;
        }
    }
    for(int i=0; i<count0; i++)
    {
        head->data = 0;
        head = head->link;
    }
    for(int i=0; i<count1; i++)
    {
        head->data = 1;
        head = head->link;
    }
    for(int i=0; i<count2; i++)
    {
        head->data = 2;
        head = head->link;
    }
}

2. Moving Nodes to front & end of list.

For each Node in the list.
 - If it has 0
      Move to the Front of list
 - If it has 2
      Move to the End of list
 - If it has 1
      Do nothing.

 Code:

/**
 * Sorts a Special list where each Node is either 0, 1 or 2.
 * Will bring all the zeros toward the head, All 2's toward the tail
 * and leave all the 1's as it is.
 *
 * head passed by reference, because it may change.
 */
void sortList(Node*& head)
{
    // Single element list is already sorted
    if(head == NULL || head->link == NULL)
        return;
    // pointer to last node in the list
    Node* last = head;
    int numOfNodes = 1;
    while(last->link != NULL)
    {
        last = last->link;
        numOfNodes++;
    }
    Node *tail = last;
    Node *ptr = head;
    Node *prev = head;
    for(int i=0; i<numOfNodes; i++)
    {
        Node* temp = ptr;
        ptr = ptr->link;
        if(temp->data == 0)
        {
            // Inserting at head (If First Node - Skip)
            if(prev != temp)
            {
                temp->link = head;
                head = temp;
                prev->link = ptr;
            }
        }
        else if(temp->data == 2)
        {
            // Inserting at the End.
            tail->link = temp;
            temp->link = NULL;
            tail = temp;
            // If first Node.
            if(prev == temp)
                head = prev = ptr;
            else
                prev->link = ptr;
        }
        else
        {
            if(prev != temp)
                prev = prev->link;
        }
    }
}

Time Complexity: Both the solutions takes O(n) time.
Extra space used: O(1) – Constant.