#include<iostream>
using namespace std;

struct node
{
	int data ;
	node * next ;
};

class list
{
	private : 
	node *head ;
	public : 
	list()
	{
		head = NULL ;
	}
	void add(int x)
	{
		node *t = head;
		node * temp = new node();
		temp -> data = x ;
		if(t==NULL)
		{
			temp->next = NULL;
			head = temp ;
		}
		else
		{	
			while(t->next !=NULL)
			{	
				t = t->next ;
			}
			temp->next = t->next ;
			t->next = temp ;
		}
		return ;
	}
	int remove()
	{
		node *t = head ;
		int a = t->data ;
		head = t->next ;
		delete t; 
		return a ;
	}
	int is_empty()
	{
		if(head==NULL)
			return 1;
		else
			return 0 ;
	}
	node * view_head()
	{
		return head ;
	}
	void print()
	{
		node * t = head ;
		while(t!=NULL)
		{
			cout << t->data << " " ;
			t = t->next;
		}
	}
};
int max_digit(list &l)
{
	int a , dig=0 ,i ;
	node *t = l.view_head() ;
	a = t->data ;
	while(t!=NULL)
	{
		if(a < t->data)
			a = t->data ;
		t= t->next ;
	}
	while(a>0)
	{
		a = a/10;
		dig++;
	}
	return dig ;
}
int pow(int a , int b)
{
	int ans = 1;
	while(b--)
	{
		ans = ans*a ;
	}
	return ans ;
}
void radix_sort(list & l , list r[])
{
	int i = 1  , j , a  , b;
	int num = max_digit(l);
	while(i<=num)
	{
		while(!l.is_empty())
		{
			a = l.remove() ;
			b = a%pow(10,i);
			b = b/pow(10,i-1);
			r[b].add(a);
		}
		for(j=0;j<10;j++)
		{
			while(!r[j].is_empty())
			{	
				a = r[j].remove();
				l.add(a);
			}
		}
		i++;
	}
}
		
int main()
{
	list l  , r[10];
	int a ;
	char ch = 'y' ;
	while(ch=='y')
	{
		cout << "Enter a number : ";
		cin >> a ;
		l.add(a);
		cout << "Enter another number ? : ";
		cin >> ch ;
	}
	cout << "List is : " ; l.print();
	radix_sort(l , r );
	cout << "\nSorted list is : " ; l.print();
	return 0 ;
}