text: Sort a linked list of 0 s , 1 s and 2 s | C Program to sort a linked list 0 s , 1 s or 2 s ; Link list node ; Function to sort a linked list of 0 s , 1 s and 2 s ; Initialize count of '0' , '1' and '2' as 0 ; 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 ; Let say count [ 0 ] = n1 , count [ 1 ] = n2 and count [ 2 ] = n3 * now start traversing list from head node , * 1 ) fill the list with 0 , till n1 > 0 * 2 ) fill the list with 1 , till n2 > 0 * 3 ) fill the list with 2 , till n3 > 0 ; Function to push a node ; allocate node put in the data ; link the old list off the new node ; move the head to point to the new node ; Function to print linked list ; Driver program to test above function ; Constructed Linked List is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 8 -> 9 -> null
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE struct Node { int data ; struct Node * next ; } ; void sortList ( struct Node * head ) { int count [ 3 ] = { 0 , 0 , 0 } ; struct Node * ptr = head ; while ( ptr != NULL ) { count [ ptr -> data ] += 1 ; ptr = ptr -> next ; } int i = 0 ; ptr = head ; while ( ptr != NULL ) { if ( count [ i ] == 0 ) ++ i ; else { ptr -> data = i ; -- count [ i ] ; ptr = ptr -> next ; } } } void push ( struct Node * * head_ref , int new_data ) { struct Node * new_node = ( struct Node * ) malloc ( sizeof ( struct Node ) ) ; new_node -> data = new_data ; new_node -> next = ( * head_ref ) ; ( * head_ref ) = new_node ; } void printList ( struct Node * node ) { while ( node != NULL ) { printf ( " % d ▁ " , node -> data ) ; node = node -> next ; } printf ( " n " ) ; } int main ( void ) { struct Node * head = NULL ; push ( & head , 0 ) ; push ( & head , 1 ) ; push ( & head , 0 ) ; push ( & head , 2 ) ; push ( & head , 1 ) ; push ( & head , 1 ) ; push ( & head , 2 ) ; push ( & head , 1 ) ; push ( & head , 2 ) ; printf ( " Linked ▁ List ▁ Before ▁ Sorting STRNEWLINE " ) ; printList ( head ) ; sortList ( head ) ; printf ( " Linked ▁ List ▁ After ▁ Sorting STRNEWLINE " ) ; printList ( head ) ; return 0 ; }