Python Program For Sorting A Linked List Of 0s, 1s And 2s

Python Program For Sorting A Linked List Of 0s, 1s And 2s

If you are referring to the problem of sorting a linked list containing only the elements 0, 1, and 2 (similar to the Dutch national flag problem), you can approach it using the following methods:

  1. Counting the number of 0s, 1s, and 2s, and then reconstructing the linked list.
  2. Using the Dutch national flag algorithm (but that's more relevant for arrays than linked lists).

Here's the solution using the first method:

class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node def printList(self): temp = self.head while temp: print(temp.data, end=" -> ") temp = temp.next print("None") def sortList(self): count = [0, 0, 0] # Count of [0s, 1s, 2s] ptr = self.head # Count the number of 0s, 1s and 2s while ptr: count[ptr.data] += 1 ptr = ptr.next i = 0 ptr = self.head while ptr: if count[i] == 0: i += 1 continue ptr.data = i count[i] -= 1 ptr = ptr.next # 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(0) print("Linked List before sorting") llist.printList() llist.sortList() print("\nLinked List after sorting") llist.printList()

This program first counts the number of 0s, 1s, and 2s, and then updates the linked list with that count.

More Tags

operands dom-events pessimistic-locking clock .net-2.0 formbuilder configuration-management sorting webclient android-4.4-kitkat

More Programming Guides

Other Guides

More Programming Examples