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 code ; Constructed Linked List is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 8 -> 9 -> null
#include <bits/stdc++.h> NEW_LINE using namespace std ; class Node { public : int data ; Node * next ; } ; void sortList ( Node * head ) { int count [ 3 ] = { 0 , 0 , 0 } ; 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 ( Node * * head_ref , int new_data ) { Node * new_node = new Node ( ) ; new_node -> data = new_data ; new_node -> next = ( * head_ref ) ; ( * head_ref ) = new_node ; } void printList ( Node * node ) { while ( node != NULL ) { cout << node -> data << " ▁ " ; node = node -> next ; } cout << endl ; } int main ( void ) { 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 ) ; cout << " Linked ▁ List ▁ Before ▁ Sorting STRNEWLINE " ; printList ( head ) ; sortList ( head ) ; cout << " Linked ▁ List ▁ After ▁ Sorting STRNEWLINE " ; printList ( head ) ; return 0 ; }