# Sort a Linked List of 0s, 1s and 2s

### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

In this question, we are given a singly linked list, which only contains 0's, 1's and 2's. We have to sort the given list in non-decreasing order.

### Problem Statement Understanding

Let’s try to understand the problem statement with the help of examples.

Suppose the given linked list is: 1 → 1 → 0 → 2 → 2.

• Now, according to the problem statement we have to sort the given linked list such that after sorting the final linked list will look like: 0 → 1 → 1 → 2 → 2.
• So basically, we will have to sort our linked list such that all the nodes with value 0 comes before the nodes with value 1 and all the nodes with value 1 comes before the nodes with value 2.

If the given linked list is: 1 → 0 → 0 → 2 → 2 → 1 → 0 → 2 → 2.

• Then, in this case, our output sorted linked list will be: 0 → 0 → 0 → 1 → 1 → 2 → 2 → 2 → 2.

Some more examples:
Sample Input 1: 2 → 2 → 1 → 0
Sample Output 1: 0 → 1 → 2 → 2

Sample Input 2: 0 → 2 → 1 → 1
Sample Output 2: 0 → 1 → 1 → 2

Sample Input 3: 1 → 1 → 0 → 2 → 2
Sample Output 3: 0 → 1 → 1 → 2 → 2

Now I think from the above examples, the problem statement is clear. So let's see how we will approach it.

Before moving to the approach section, try to think, how should we approach this problem?

• One simple way is to sort the linked list using any sorting algorithm (choose wisely). It will do our work, but our complexity will be O(nlog(n)), and also we should keep in mind that in our problem there are only three values possible (0, 1 and 2), so we should also utilize this information.

Instead of directly applying sorting on the linked list, try to think of some better way to sort the list. Will it be helpful if we count the number of 0's, 1's and 2's?

• Yes, it will be very helpful. Our approach is going to make use of this count.

Let us have a glance at the approach.

### Approach

Our approach is going to be pretty simple.

• We will traverse the list and count the number of 0's, 1's and 2's. Now, how will counting be helpful to us? Well, after counting, let the number of 0's be x, the number of 1's be y and the number of 2's be z.
• Now, with the help of the counts, we will traverse the list again and fill the first x nodes with 0, then next y nodes with 1 and then next z nodes with 2.
• If we notice carefully, this will make our list sorted, as 0's will come first, then 1's and finally 2's. Hence, our objective to sort the linked list.

### Algorithm

• Create an array cnt , which will have a size of 3 and all the elements will initially be 0.
• Create a node ptr and point it to the head of the list. This pointer ptr will be used to traverse the list.
• Now, traverse the list and for every node do, cnt [ ptr - > data ] + = 1.
• In the above step, if ptr -> data is 0, then the value at 0th index of the array will increase and hence, the indexes 0, 1 and 2 will contain the number of 0's, 1's and 2's respectively.
• Now, create a variable i and initialize it with 0. This i will be the element that will be inserted in the nodes, i.e., 0, 1 or 2.
• Now, make the ptr point to the head again, as we need to traverse the list again.
• In the loop while traversing:
• if count[i] = 0, we will increment i.
• Else we will make ptr -> data = i and decrement count[i]. What is the significance of this?
• Suppose count is 3. Now, For the first 3 iterations, ptr -> data will be equal to 0.
• As the count is getting decreased in every iteration, after 3 iterations, the count will be 0, so now, we will increment i as now we have to fill the next y (where y is the number of nodes with data 1) nodes with 1. The same process will get repeated with 1's and 2's.
• Finally, our list will get sorted.

### Dry Run   ### Code Implementation

```#include
using namespace std;

class Node
{
public:
int data;
Node* next;
};

/* We will use this function to sort the linked list containing 0's, 1's and 2's */
{
int count = {0, 0, 0};

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

int i = 0;

while (ptr != NULL)
{
if (count[i] == 0)
++i;
else
{
ptr->data = i;
--count[i];
ptr = ptr->next;
}
}
}

/* This function is used to insert nodes at head of the linked list */
void push (Node** head, int new_data)
{

Node* new_node = new Node();

new_node->data = new_data;

}

/* This function is used to print the linked list */
void print(Node *node)
{
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
cout << endl;
}

int main(void)
{

cout << "Initial Linked List Before Sorting\n";

cout << "Resultant Linked List After Sorting\n";

return 0;
}
```
```public class LinkedList
{

class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
/* We will use this function to sort the linked list containing 0's, 1's and 2's */
void sort()
{

int count[] = {0, 0, 0};

while (ptr != null)
{
count[ptr.data]++;
ptr = ptr.next;
}

int i = 0;

while (ptr != null)
{
if (count[i] == 0)
i++;
else
{
ptr.data= i;
--count[i];
ptr = ptr.next;
}
}
}

/* This function is used to insert nodes at head of the linked list */
public void push(int new_data)
{
Node new_node = new Node(new_data);

}

/* This function is used to print the linked list */
void print()
{
while (temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}
public static void main(String args[])
{
llist.push(2);
llist.push(2);
llist.push(0);
llist.push(1);
llist.push(1);

llist.print();

llist.sort();

llist.print();
}
}
```