Sort the linked list of 0s, 1s and 2s

Sort the linked list of 0s, 1s and 2s

In this, we are given a linked list of 0s, 1s, and 2s, and we need to sort it.

Examples:

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

Output:

0  ->  0  ->  1  ->  1  ->  1  ->  2  ->  2  ->  NULL

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

Output:

0  ->  1  ->  1  ->  1  ->  2  ->  NULL

Method:

This method sorts the list using the below steps:

• Firstly, we will traverse the entire list and then count 0s, 1s, and 2s. Assume they are n1, n2, and n3, respectively.
• Now, we will traverse the linked list again and fill the first n1 nodes with 0, n2 nodes with 1, and n2 nodes with 2.

C Program to sort a linked list of 0s, 1s or 2s

 #include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node * next;
};
struct node * start = NULL;
// For inserting the elements in the linked list
void add(int item)
{
struct node * t, * p;
t = (struct node *)malloc( sizeof( struct node ));
if(start == NULL)
{
start = t;
start -> info = item;
start -> next = NULL;
return;
}
else
{
struct node * p = start;
while(p -> next != NULL)
{
p = p -> next;
}
p -> next = t;
p = p -> next;
p -> info = item;
p -> next = NULL;
}
}
// For sorting the linked list of 0s, 1s and 2s
void sortList(struct node * head)
{
    int count[3] = {0, 0, 0};  // Initialize count of '0', '1' and '2' as 0
    struct node * ptr = head;
    while (ptr != NULL)
    {
        count[ptr -> info] += 1;
        ptr = ptr -> next;
    }
    int i = 0;
    ptr = head;
    while (ptr != NULL)
    {
        if (count[i] == 0)
            ++i;
        else
        {
            ptr->info = i;
            --count[i];
            ptr = ptr -> next;
        }
    }
}
// To display the elements of the linked list
void traverse(struct node * t)
{
if(t == NULL)
{
            printf(" Linked list is empty\n");
                                    }
                                    while(t -> next != NULL)
                                    {
                        printf("%d -> ",t -> info);
                        t = t -> next;
                        }
                        printf("%d\n",t -> info);
}
// Driver Function
int main()
{
    add(1);
    add(0);
    add(2);
    add(0);
    add(1);
    add(1);
    add(2);
    add(2);
   add(0);
   add(1);
    printf("Given Linked List: \n");
    traverse(start);
    sortList (start);
    printf("Linked List After sorting: \n");
    traverse(start);
    return 0;
} 

Output:

Time Complexity: The time complexity of this method is O(n), where n is the number of nodes in the linked list.

Auxiliary Space: The time complexity of this method is O(1).