Javascript Program For Sorting A Linked List Of 0s, 1s And 2s
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:
Javascript
<script> // Javascript program to sort a // linked list of 0, 1 and 2 // Head of list var head; // Linked list Node class Node { constructor(val) { this .data = val; this .next = null ; } } function sortList() { // Initialise count of 0 1 // and 2 as 0 var count = [ 0, 0, 0 ]; var ptr = 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 != null ) { count[ptr.data]++; ptr = ptr.next; } var i = 0; ptr = 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 != null ) { if (count[i] == 0) i++; else { ptr.data = i; --count[i]; ptr = ptr.next; } } } // Utility functions /* Inserts a new Node at front of the list. */ function push(new_data) { /* 1 & 2: Allocate the Node & Put in the data */ var new_node = new Node(new_data); // 3. Make next of new Node as head new_node.next = head; // 4. Move the head to point to // new Node head = new_node; } // Function to print linked list function printList() { var temp = head; while (temp != null ) { document.write(temp.data + " " ); temp = temp.next; } document.write( "<br/>" ); } // Driver code /* Constructed Linked List is 1->2->3->4->5->6->7-> 8->8->9->null */ push(0); push(1); push(0); push(2); push(1); push(1); push(2); push(1); push(2); document.write( "Linked List before sorting<br/>" ); printList(); sortList(); document.write( "Linked List after sorting<br/>" ); printList(); // This code is contributed by todaysgaurav </script> |
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!
Contact Us