Write code to sort a linked list of 0s, 1s and 2s. Given a linked list which only consists of 0s, 1s and 2s. Write a function to sort a linked list.
For example:
Input: 2 -> 0 -> 1 -> 0 -> 2 -> 0 -> 1 -> NULL
Output: 0 -> 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> NULL
This problem is similar to sort an array of 0s, 1s and 2s. Let’s discuss how we can solve this problem in minimum time complexity.
Sort a Linked List of 0s, 1s and 2s | Java Code
There are multiple approaches we can use to solve this problem. In this tutorial, I am going to discuss an approach to count the number of 0s, 1s and 2s and then we put the nodes in a correct position.
To sort a given linked list, we need to follow these steps:
i) Count the number of 0s, 1s, and 2s present in a linked list. Let the count be n1, n2, and n3.
ii) Traverse the linked list again and fill the first n1 nodes with zero, then next n2 nodes with one and finally n3 nodes with two.
The time complexity of this approach is O(n) and its space complexity is O(1).
Programming questions on Linked List
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
//Sort a linked list public Node sortLinkedList() { int[] countArr = {0, 0, 0}; Node temp = head; //Maintain a count of 0, 1, 2 while(temp != null) { countArr[temp.data]++; temp = temp.next; } temp = head; int i = 0; //Create a linked list in sorted order while(temp != null) { if(countArr[i] == 0) { i++; } else { temp.data = i; countArr[i]--; temp = temp.next; } } return temp; } |
Complete Java code for sorting a linked list of 0s, 1s and 2s.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
//Java code to sort a linked list of 0s, 1s and 2s. public class SortLinkedList { private Node head; public SortLinkedList() { this.head = null; } public Node sortLinkedList() { int[] countArr = {0, 0, 0}; Node temp = head; while(temp != null) { countArr[temp.data]++; temp = temp.next; } temp = head; int i = 0; while(temp != null) { if(countArr[i] == 0) { i++; } else { temp.data = i; countArr[i]--; temp = temp.next; } } return temp; } public static void main(String[] args) { SortLinkedList ll = new SortLinkedList(); ll.insertAtEnd(2); ll.insertAtEnd(0); ll.insertAtEnd(1); ll.insertAtEnd(0); ll.insertAtEnd(2); ll.insertAtEnd(0); ll.insertAtEnd(1); ll.print(); System.out.println("\n"); ll.sortLinkedList(); ll.print(); } public void print() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } } public Node insertAtEnd(int data) { if (head == null) { head = new Node(data); } else { Node node = head; while(node.next != null) { node = node.next; } //Points to new node node.next = new Node(data); } return head; } } |
