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

0 0 2 minutes read

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!

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 zambiatek!