Not an optimized solution for space complexity. Just giving it a shot.O(n) space


#1

ListNode* Solution::solve(ListNode* A) {
ListNode *k=NULL,*p=NULL;
int c=0,d=0;
while(A!=NULL){
if(A->val==0) c++;
else d++;
A=A->next;
}
//cout<<c<<" "<<d;
k=new ListNode(-1);
p=k;
while(c!=0){
k->next=new ListNode(0);
c–;
k=k->next;
}
while(d!=0){
k->next=new ListNode(1);
d–;
k=k->next;
}
k->next=NULL;
return p->next;
}