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).