Sort a linked list of 0 s , 1 s and 2 s | head of list ; Linked list Node ; initialise 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 ; Inserts a new Node at front of the list . ; * 1 & 2 : Allocate the Node & Put in the data ; 3. Make next of new Node as head ; 4. Move the head to point to new Node ; Function to print linked list ; Constructed Linked List is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 8 -> 9 -> null
var head ; class Node { constructor ( val ) { this . data = val ; this . next = null ; } } function sortList ( ) { var count = [ 0 , 0 , 0 ] ; var ptr = head ; while ( ptr != null ) { count [ ptr . data ] ++ ; ptr = ptr . next ; } var i = 0 ; ptr = head ; while ( ptr != null ) { if ( count [ i ] == 0 ) i ++ ; else { ptr . data = i ; -- count [ i ] ; ptr = ptr . next ; } } } function push ( new_data ) { var new_node = new Node ( new_data ) ; new_node . next = head ; head = new_node ; } function printList ( ) { var temp = head ; while ( temp != null ) { document . write ( temp . data + " " ) ; temp = temp . next ; } document . write ( " " ) ; } push ( 0 ) ; push ( 1 ) ; push ( 0 ) ; push ( 2 ) ; push ( 1 ) ; push ( 1 ) ; push ( 2 ) ; push ( 1 ) ; push ( 2 ) ; document . write ( " " ) ; printList ( ) ; sortList ( ) ; document . write ( " " ) ; printList ( ) ;