#include <cstdlib>

#include <cstdio>

using namespace std;

struct Node {

int data;

struct Node *next;

Node(int _data):data(_data), next(NULL){}

};

typedef Node *List;

/*

* Algo:

* Divide the list into 3 different lists,

* list1 having all 1's, list2 having all 2's and list3 having all 3's

* Concatenate list1, list2 and list3

*/

List sort(List l){

List start1 = NULL, start2 = NULL, start3 = NULL;

if(!l)

return start1;

Node *n1 = NULL, *n2 = NULL, *n3 = NULL;

while(l){

switch(l->data){

case 1:

if(n1){

n1->next = l;

} else{

start1 = l;

}

n1 = l;

break;

case 2:

if(n2){

n2->next = l;

} else {

start2 = l;

}

n2 = l;

break;

case 3:

if(n3){

n3->next = l;

}else {

start3 = l;

}

n3 = l;

break;

}

l = l->next;

}

if(n1)

n1->next = start2;

if(n2)

n2->next = start3;

if(n3)

n3->next = NULL;

return start1 ? start1 : start2 ? start2 : start3;

}

List append(List l, int n){

Node *node = new Node(n);

if(!l) return node;

Node *p = l;

while(p->next)

p = p->next;

p->next = node;

return l;

}

void print(List l) {

while(l){

printf("%d ", l->data);

l = l->next;

}

printf("\n");

}

/*

*

*/

int main(int argc, char** argv) {

int n, num;

scanf("%d", &n);

List l = NULL;

for(int i = 0; i < n; ++i){

scanf("%d", &num);

l = append(l, num);

}

print(l);

l = sort(l);

print(l);

return 0;

}

Advertisements