Sort a linked list of 0 s , 1 s and 2 s | Java program to sort a linked list of 0 , 1 and 2 ; 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 ; Driver program to test above functions ; Constructed Linked List is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 8 -> 9 -> null
class LinkedList { Node head ; class Node { int data ; Node next ; Node ( int d ) { data = d ; next = null ; } } void sortList ( ) { int count [ ] = { 0 , 0 , 0 } ; Node ptr = head ; while ( ptr != null ) { count [ ptr . data ] ++ ; 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 ; } } } public void push ( int new_data ) { Node new_node = new Node ( new_data ) ; new_node . next = head ; head = new_node ; } void printList ( ) { Node temp = head ; while ( temp != null ) { System . out . print ( temp . data + " ▁ " ) ; temp = temp . next ; } System . out . println ( ) ; } public static void main ( String args [ ] ) { LinkedList llist = new LinkedList ( ) ; llist . push ( 0 ) ; llist . push ( 1 ) ; llist . push ( 0 ) ; llist . push ( 2 ) ; llist . push ( 1 ) ; llist . push ( 1 ) ; llist . push ( 2 ) ; llist . push ( 1 ) ; llist . push ( 2 ) ; System . out . println ( " Linked ▁ List ▁ before ▁ sorting " ) ; llist . printList ( ) ; llist . sortList ( ) ; System . out . println ( " Linked ▁ List ▁ after ▁ sorting " ) ; llist . printList ( ) ; } }