## In the given linked list, which contains only 0s, 1s or 2s. Write a function to sort the linked list.

### Example

**Time complexity : O(n)**

## Algorithm

**a.** Create a count array of size 3,

count[1] stores count of 0

count[1] stores count of 1

count[2] stores count of 2

**b.** Traverse in the linked list count the number of 0s, 1s and 2s. Let counts be c0, c1 and c2.

**c.** Traverse the linked list again and fill it with 0s first c0 nodes, 1s with next c1 nodes and last c2 nodes with 2s.

### Algorithm working

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
struct LLNode
{
int data;
struct LLNode* next;
};
//Function to sort linked list
void SortLL(struct LLNode *head)
{
//count array to store count of 0s, 1s and 2s
//temp is pointer to traverse in the array
int count[3] = {0, 0, 0};
struct LLNode *temp = head;
while (temp != NULL)
{
count[temp->data] += 1;
temp = temp->next;
}
//Traverse in the array and fill with 0s, 1s and 2s
//first count[0] places with 0s
//second count[1] places with 1s
//last count[2] places with 2s
int i = 0;
temp = head;
while (temp != NULL)
{
if (count[i] == 0)
{
i = i + 1;
}
else
{
temp->data = i;
count[i] = count[i] - 1 ;
temp = temp->next;
}
}
}
/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
struct LLNode* curr = new LLNode;
curr->data = dataToBeInserted;
curr->next = NULL;
if(*head == NULL)
*head=curr; //if this is first node make this as head of list
else
{
curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
*head=curr;
}
//O(1) constant time
}
//display linked list
void display(struct LLNode**node)
{
struct LLNode *temp= *node;
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;
temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}
//Main function
int main(void)
{
struct LLNode *head = NULL;
insertAtBeginning(&head, 0);
insertAtBeginning(&head, 1);
insertAtBeginning(&head, 0);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 1);
insertAtBeginning(&head, 1);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 1);
insertAtBeginning(&head, 2);
cout<<"Input linked list: ";
display(&head);
SortLL(head);
cout<<"\nOutput linked list after sorting\n";
display(&head);
return 0;
}
```

Try It

**Next >**
**< Prev**