Microsoft Interview Question:Sort a list of 0's ,1's and 2's solution in java

Solution:

 Traverse the list and count the number of 0s, 1s and 2s.
 Let the counts be node1, node2 and node3 respectively.
 Traverse the list again, fill the first node1 nodes with 0, then node2 nodes with 1 and finally node3 nodes with 2 .

Sample code:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class SortLinkedList
{
Node head;

class Node
{
int data;
Node next;

public Node(int d) {

this.data=d;
next=null;
}
}

void push(int new_data)
{
Node node=new Node(new_data);
node.next=head;
head=node;
}

void printList()
{
Node temp=head;
while(temp!=null)
{
System.out.println(temp.data + " ");
temp=temp.next;
}
System.out.println();
}

void sortList()
{
int count[]={0,0,0};
Node ptr=head;
while(ptr!=null)
{
count[ptr.data]++;
ptr=ptr.next;
}

int i=0;
ptr=head;

while(ptr!=null)
{
if(count[i]==0)
i++;
else
{
ptr.data=i;
   --count[i];
   ptr=ptr.next;
}
}

}

public static void main(String[] args) {
// TODO Auto-generated method stub

SortLinkedList list=new SortLinkedList();
list.push(0);
list.push(1);
list.push(0);
list.push(2);
        list.push(1);
        list.push(1);
        list.push(2);
        list.push(1);
        list.push(2);
       
        System.out.println("Linked List before sorting");
        list.printList();
       
        list.sortList();

        System.out.println("Linked List after sorting");
        list.printList();
}

}

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 

Solution Complexity: 

Time Complexity: O(n) where n is number of nodes in linked list.

Auxiliary Space: O(1)