27. Given a linked list of 0's, 1's and 2's, sort it

27. Given a linked list of 0's, 1's and 2's, sort it

Problem link :- click here

package Linked_List;

public class LinkedList__27
{

	/*
		 Given a linked list of n nodes where nodes can contain values 0s, 1s and 2s only.
		 The task is to segregate 0s, 1s and 2s linked list such that all zeros segregate to
		 head side, 2s at the end of the linked list, and 1s in the mid of 0s and 2s.
		 			input :	1, 2, 2, 1, 2, 0, 2, 2
		 			output :	0, 1, 1, 2, 2, 2, 2, 2
		 	
		 1 -> Lets create an array of size 3 to store the number of zero's, one's and two's.
		 2 -> iterate through the linked list and update array.
		 3 -> now iterate through the linked list and change the values of the nodes using 
		 	the count array.
	*/
	
	static void sort012(LinkedList list)
	{
		//step 1 :-
		int count[] = new int[3];
		for(int i=0; i<3; i++)
			count[i] = 0;
		
		//step 2 :- 
		Node temp = list.head;
		for(temp=list.head; temp!=null; temp=temp.next)
		{
			count[temp.data]++;
		}
		
		//step 3 :- 
		temp = list.head;
		int i = 0;
		while(temp!=null)
		{
			if(count[i] == 0)
				i++;
			else
			{
				temp.data = i;
				count[i]--;
				temp = temp.next;
			}
		}
	}
	
	static void sort012LinkedList(LinkedList list)
	{
		if(list.head == null   ||   list.head.next == null)
			return;
		
		int count0 = 0;
		int count1 = 0;
		int count2 = 0;
		for(Node temp=list.head; temp!=null; temp=temp.next)
		{
			if(temp.data == 0)
				count0++;
			else if(temp.data == 1)
				count1++;
			else
				count2++;
		}
		
		for(Node temp=list.head; temp!=null; temp=temp.next)
		{
			if(count0 > 0)
			{
				temp.data = 0;
				count0--;
			}
			else if(count0 == 0  &&   count1 > 0)
			{
				temp.data = 1;
				count1--;
			}
			else if(count0 == 0  &&  count1 == 0   &&  count2 >0)
			{
				temp.data = 2;
				count2--;
			}
		}
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(1);
		list.push(2);
		list.push(2);
		list.push(1);
		list.push(2);
		list.push(0);
		list.push(2);
		list.push(2);
		
		System.out.println("Linked list before sorting : ");
		printList(list);
		
		sort012LinkedList(list);
		System.out.println("\nLinked list after sorting : ");
		printList(list);
	}

	static void printList(LinkedList list)
	{
		for(Node temp=list.head; temp!=null; temp=temp.next)
			System.out.print(temp.data + "-> ");
		System.out.println("null");
	}
}

Time complexity :- O(n)
Space complexity :- O(1)