Sort a linked list of 0 s , 1 s and 2 s | Python 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 ; Constructed Linked List is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 8 -> 9 -> null
class LinkedList ( object ) : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . head = None NEW_LINE DEDENT class Node ( object ) : NEW_LINE INDENT def __init__ ( self , d ) : NEW_LINE INDENT self . data = d NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def sortList ( self ) : NEW_LINE INDENT count = [ 0 , 0 , 0 ] NEW_LINE ptr = self . head NEW_LINE while ptr != None : NEW_LINE INDENT count [ ptr . data ] += 1 NEW_LINE ptr = ptr . next NEW_LINE DEDENT i = 0 NEW_LINE ptr = self . head NEW_LINE while ptr != None : NEW_LINE INDENT if count [ i ] == 0 : NEW_LINE INDENT i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT ptr . data = i NEW_LINE count [ i ] -= 1 NEW_LINE ptr = ptr . next NEW_LINE DEDENT DEDENT DEDENT def push ( self , new_data ) : NEW_LINE INDENT new_node = self . Node ( new_data ) NEW_LINE new_node . next = self . head NEW_LINE self . head = new_node NEW_LINE DEDENT def printList ( self ) : NEW_LINE INDENT temp = self . head NEW_LINE while temp != None : NEW_LINE INDENT print str ( temp . data ) , NEW_LINE temp = temp . next NEW_LINE DEDENT print ' ' NEW_LINE DEDENT DEDENT llist = LinkedList ( ) NEW_LINE llist . push ( 0 ) NEW_LINE llist . push ( 1 ) NEW_LINE llist . push ( 0 ) NEW_LINE llist . push ( 2 ) NEW_LINE llist . push ( 1 ) NEW_LINE llist . push ( 1 ) NEW_LINE llist . push ( 2 ) NEW_LINE llist . push ( 1 ) NEW_LINE llist . push ( 2 ) NEW_LINE print " Linked ▁ List ▁ before ▁ sorting " NEW_LINE llist . printList ( ) NEW_LINE llist . sortList ( ) NEW_LINE print " Linked ▁ List ▁ after ▁ sorting " NEW_LINE llist . printList ( ) NEW_LINE