# Sort 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 : 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> 0
Output : 0 -> 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2

Solution:
You can do that in O(n).

Traverse the linked list from the beginning and count the number of 0s, 1s and 2s. (Let the counts be p, q, r)
Now traverse the linked list again and set first p nodes to 0, q nodes to 1 and r nodes to 2.

```/* Link list node */
struct node
{
int data;
};

// Function to sort a linked list of 0s, 1s and 2s
void sortList(struct node *start)
{
int count[3] = {0, 0, 0};
struct node *ptr = start;

/* count total number of '0', '1' and '2'
* count[0] will store total number of '0's
* count[1] will store total number of '1's
* count[2] will store total number of '2's  */
while (ptr)
{
count[ptr->data] += 1;
}

int i = 0;
ptr = start;

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

```

### One Thought on “Sort a Linked List of 0s, 1s and 2s”

1. Nancy Goyal on May 7, 2015 at 7:00 pm said:

The above program will not give the desired output.
There is a bug in this program. The sortList function should go like this
void sortList(struct node *start)
10 {
11 int count[3] = {0, 0, 0};
12 struct node *ptr = start;
13
14 /* count total number of ’0′, ’1′ and ’2′
15 * count[0] will store total number of ’0′s
16 * count[1] will store total number of ’1′s
17 * count[2] will store total number of ’2′s */
18 while (ptr)
19 {
20 count[ptr->data] += 1;
22 }
23
24 int i = 0;
25 ptr = start;
26
27 while (ptr)
28 {
29 if (count[i] == 0)
30 ++i;
31 //else //This piece of code in else part should execute every iterate
32 //{
33 ptr->data = i;
34 count[i]–;