1.

Write a function to sort a linked list of 0s, 1s and 2s

Answer»


  • Input: 0->1->0->2->1->0->2->1


  • Output: 0->0->0->1->1->1->2->2


  • Explanation: All 0’s will come first then 1s and then 2s. This can be done in O(n) time by counting the occurrences of all three and rearranging them in the linked list.

//structure of the linked list
struct Node {
int data;
Node *left;
Node *right;
}
//function take the head of the linked list as a parameter
void sortList(Node *head)
{
//if linked list is empty then return back
if(head==NULL)
return;
else
{
Node *temp=head;
Node *temp1=head;
//to store count of 0s, 1s, and 2s
int count0=0,count1=0,count2=0;
//calculating the count of 0s, 1s, and 2s
while(temp!=NULL)
{
if(temp->data==0)
count0++;
else if(temp->data==1)
count1++;
else
count2++;
temp=temp->next;
}
//iterating over count of 0s and filling the linked list
while(count0!=0)
{
temp1->data=0;
temp1=temp1->next;
count0--;
}
//iterating over count of 1s and filling the linked list
while(count1!=0)
{
temp1->data=1;
temp1=temp1->next;
count1--;
}
//iterating over count of 2s and filling the linked list
while(count2!=0)
{
temp1->data=2;
temp1=temp1->next;
count2--;
}
}
}


  • Time Complexity: O(n)


  • Space Complexity: O(1)


Discussion

No Comment Found

Related InterviewSolutions