Linked List: Sort a linked list of 0, 1, 2

Problem Statement:

Given a linked list of 0, 1, 2, you need to sort it as ascending order.

Example:

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

Solution 1:

Count the number of 0 1 and 2.

THen traverse list, then fill the list of 0 1 and 2.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream> 
using namespace std;

class Node 
{
  public:
    int data;
    Node *next;
   
    Node(int new_data) 
    {
        data = new_data;
        next = NULL;
    }
};

void solution_1 (Node* head) 
{

    int count[3] = {0, 0, 0};
    Node *ptr = head;

    while (ptr != NULL) 
    {
        count[ptr->data] += 1;
        ptr = ptr->next;
    }

    int idx = 0;
    ptr = head;

    while (ptr != nullptr) 
    {

        if (count[idx] == 0)
            idx += 1;
        else {
            ptr->data = idx;
            count[idx] -= 1;
            ptr = ptr->next;
        }
    }
}

void print_list(Node *node) 
{
    while (node != nullptr) 
    {
        cout << " " << node->data;
        node = node->next;
    }
    cout << "\n";
}


int main() 
{

    Node *head = new Node(1);
    head->next = new Node(1);
    head->next->next = new Node(2);
    head->next->next->next = new Node(1);
    head->next->next->next->next = new Node(0);

    cout << "Before Sorting:";
    print_list(head);

    solution_1(head);

    cout << "After Sorting:";
    print_list(head);

    return 0;
}

Output

Before Sorting: 1 1 2 1 0
After Sorting: 0 1 1 1 2