#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct node {
int data;
struct node* link;
};
struct node* createnode(int data) {
struct node* temp;
temp = (struct node*)malloc(sizeof(struct node));
temp->data = data;
temp->link = NULL;
return temp;
}
void printll(struct node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->link;
}
printf("\n");
}
struct node* sort(struct node* head, int size) {
int d = 10;
for (int i = 1; i <= size; i++, d *= 10) {
struct node* a[10];
for (int k = 0; k < 10; k++) {
a[k] = NULL;
}
while (head != NULL) {
struct node* next = head->link;
int digit = (head->data / d) % 10;
if (a[digit] == NULL) {
a[digit] = head;
} else {
struct node* curr = a[digit];
while (curr->link != NULL) {
curr = curr->link;
}
curr->link = head;
}
head->link = NULL;
head = next;
}
head = a[0];
for (int j = 1; j < 10; j++) {
if (a[j] == NULL) {
continue;
} else {
struct node* temp = head;
while (temp->link != NULL) {
temp = temp->link;
}
temp->link = a[j];
}
}
}
return head;
}
int main() {
int n;
printf("enter the size of array ");
scanf("%d", &n);
int x, max = -1;
struct node* head = NULL;
struct node* tail = NULL;
while (n--) {
printf("enter the no ");
scanf("%d", &x);
if (x > max) {
max = x;
}
struct node* curr = createnode(x);
if (head == NULL) {
head = curr;
tail = curr;
} else {
tail->link = curr;
tail = curr;
}
}
int size = 0;
while (max != 0) {
max = max / 10;
size++;
}
printf("before Sorting\n");
printll(head);
head = sort(head, size);
printf("After sorting\n");
printll(head);
return 0;
}