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