Given a linked list of 0s, 1s and 2s, sort it.
Examples:
Input: 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> NULL Output: 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 -> NULL Input: 1 -> 1 -> 2 -> 1 -> 0 -> NULLĀ Output: 0 -> 1 -> 1 -> 1 -> 2 -> NULL
Source: Microsoft Interview | Set 1
Following steps can be used to sort the given linked list.
- Traverse the list and count the number of 0s, 1s, and 2s. Let the counts be n1, n2, and n3 respectively.
- Traverse the list again, fill the first n1 nodes with 0, then n2 nodes with 1, and finally n3 nodes with 2.
Below image is a dry run of the above approach:
Below is the implementation of the above approach:
Python
# Python program to sort a linked listĀ # of 0, 1 and 2 class LinkedList(object): Ā Ā Ā Ā def __init__(self): Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Head of list Ā Ā Ā Ā Ā Ā Ā Ā Ā self.head = NoneĀ Ā Ā Ā Ā Ā # Linked list Node Ā Ā Ā Ā class Node(object): Ā Ā Ā Ā Ā Ā Ā Ā def __init__(self, d): Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā self.data = d Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā self.next = NoneĀ Ā Ā Ā Ā Ā def sortList(self): Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Initialise count of 0 1 Ā Ā Ā Ā Ā Ā Ā Ā # and 2 as 0 Ā Ā Ā Ā Ā Ā Ā Ā count = [0, 0, 0] Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ptr = self.head Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # 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Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā while ptr != None: Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count[ptr.data] += 1Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ptr = ptr.nextĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā i = 0Ā Ā Ā Ā Ā Ā Ā Ā ptr = self.head Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # 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Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā while ptr != None: Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if count[i] == 0: Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā i+=1Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā else: Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ptr.data = i Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count[i] -= 1Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ptr = ptr.nextĀ Ā Ā Ā Ā Ā Ā Ā # Utility functions Ā Ā Ā Ā # Inserts a new Node at front ofĀ Ā Ā Ā Ā # the list. Ā Ā Ā Ā def push(self, new_data): Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # 1 & 2: Allocate the Node & Ā Ā Ā Ā Ā Ā Ā Ā #Ā Ā Ā Ā Ā Ā Ā Put in the data Ā Ā Ā Ā Ā Ā Ā Ā new_node = self.Node(new_data) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # 3. Make next of new Node as head Ā Ā Ā Ā Ā Ā Ā Ā new_node.next = self.head Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # 4. Move the head to point to new Node Ā Ā Ā Ā Ā Ā Ā Ā self.head = new_node Ā Ā Ā Ā Ā Ā # Function to print linked list Ā Ā Ā Ā def printList(self): Ā Ā Ā Ā Ā Ā Ā Ā temp = self.head Ā Ā Ā Ā Ā Ā Ā Ā while temp != None: Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā print str(temp.data), Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā temp = temp.nextĀ Ā Ā Ā Ā Ā Ā Ā print '' Ā Ā # Driver code llist = 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) Ā Ā print "Linked List before sorting"llist.printList() Ā Ā llist.sortList() Ā Ā print "Linked List after sorting"llist.printList() # This code is contributed by BHAVYA JAIN |
Output:Ā
Linked List Before Sorting 2 1 2 1 1 2 0 1 0 Linked List After Sorting 0 0 1 1 1 1 2 2 2
Time Complexity: O(n) where n is the number of nodes in the linked list.Ā
Auxiliary Space: O(1)
Please refer complete article on Sort a linked list of 0s, 1s and 2s for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? Itās time for a change! Join our DSA course, where weāll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
