#include<iostream.h>
#include<stdlib.h>
typedef int elemtype;
struct lnode
{
	elemtype data;
	lnode *next;
};

void initlist ( lnode *&hl )
{
	lnode *p=new lnode;
	p->next=NULL;
	hl=p;
	hl->next=NULL;
}

void clearlist ( lnode *&hl )
{
	lnode *p,*q;
	p=hl->next;
	while ( p!=NULL )
	{
		q=p->next;
		delete p;
		p=q;
	}
	hl->next=NULL;
}

int lissize ( lnode *hl )
{
	int i=0;
	lnode *p=hl->next;
	while ( p!=NULL )
	{
		i++;
		p=p->next;
	}
	return i;
}

int listempty ( lnode *hl )
{
	return hl->next==NULL;
}
elemtype getelem ( lnode *hl,int i )
{
	if ( i<1 )
	{
		cerr<<"pos is out range!"<<endl;
		exit ( 1 );
	}
	lnode *p=hl->next;
	int j=0;
	while ( p!=NULL )
	{
		j++;
		if ( j==i )
			break;
		p=p->next;
	}
	if ( p==NULL )
	{
		cerr<<"pos is out range!"<<endl;
		exit ( 1 );
	}
	return ( p->data );
}

void insertrear ( lnode *hl,elemtype x )
{
	lnode *q=new lnode;
	q->data=x;
	q->next=NULL;
	lnode *p=hl;
	while ( p->next!=NULL )
		p=p->next;
	p->next=q;
}
void looklist ( lnode *hl )
{
	lnode *p=hl->next;
	while ( p!=NULL )
	{
		cout<<p->data<<"  ";
		p=p->next;
	}
	cout<<endl;
}

int findlist ( lnode *hl,elemtype &x )
{
	lnode *p=hl->next;
	while ( p!=NULL )
		if ( p->data==x )
		{
			x=p->data;
			return 1;
		}
		else
			p=p->next;
	return 0;
}

void insertlist ( lnode *hl,elemtype x,int i )
{
	if ( i<1 )
	{
		cerr<<"pos is out range!"<<endl;
		exit ( 1 );
	}
	lnode *p,*q;
	int j=0;
	p=hl;
	while ( p->next!=NULL )
	{
		j++;
		if ( j==i )
			break;
		p=p->next;
	}
	if ( j==i )
	{
		q=new lnode;
		q->data=x;
		q->next=p->next;
		p->next=q;
	}
	else
	{
		cerr<<"pos is out range!"<<endl;
		exit ( 1 );
	}
}

void deletelist ( lnode *hl,int i )
{
	lnode *p=hl;
	int j=0;
	while ( p->next!=NULL&&j<i-1 )
	{
		p=p->next;
		j++;
	}
	if ( j>i-1||p->next==NULL )
	{
		cerr<<"error!"<<endl;
		exit ( 1 );
	}
	lnode *q=p->next;
	p->next=q->next;
	delete q;
}
void sortlist ( lnode *hl,int k )
{
	lnode *head=new lnode;
	head->next=NULL;
	head->data=hl->next->data;
	for ( lnode *p=hl->next->next; p; p=p->next )
	{
		lnode *q=new lnode;
		q->data=p->data;
		lnode *cp=head;
		lnode *ap=NULL;
		while ( cp )
		{
			if ( k==1 )
			{
				if ( q->data<cp->data )
					break;
				else
					{ ap=cp;  cp=cp->next;}
			}
			else
			{
				if ( q->data>cp->data )
					break;
				else
					{ ap=cp;  cp=cp->next;}
			}
		}
		if ( ap==NULL )
			{ q->next=head; head=q;}
		else
			{ q->next=cp; ap->next=q;}
	}

	lnode *r=new lnode;
	r->next=head;
	head=r;
	looklist ( head );
	clearlist ( head );
}
void main( )
{
	lnode *hl;
	initlist ( hl );
	int i;
	elemtype x;
	cout<<"input in 5 num:";
	for ( i=0; i<5; i++ )
	{
		cin>>x;
		insertrear ( hl,x );
	}
	cout<<"input 2 num:";
	cin>>x;
	insertlist ( hl,x,1 );
	cin>>x;
	insertlist ( hl,x,1 );
	looklist ( hl );
	sortlist ( hl,1 );
	sortlist ( hl,0 );

}