Given a linked list and the node values range from 1 to 3.It may contain any number of nodes ,sort the list

#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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s