#include <malloc.h>
#include <stdio.h>
#include <conio.h>

#define	MALLOC(x)	malloc(sizeof(x))

typedef struct _node NODE; 
struct _node {
	int No; 
	NODE *next;
}

main()
{
NODE *H, *T, *p, *q, *r;
int	 Ans;

H=NULL;

do {
	printf("Please input a number:");
	if(H==NULL){
		H=T=MALLOC(NODE);
		T->next=NULL;
	}
	else{
		T->next=MALLOC(NODE);
		T=T->next;
		T->next=NULL;
	}
	scanf("%d", &T->No);
	printf("Continue? (Y/N)\n");
	Ans=getch();
} while(Ans=='y' || Ans=='Y');

printf("Original list: ");
p=H;
while(p!=NULL){
	printf("->%d", p->No);
	p=p->next;
}
printf("\n");

q=NULL;
while(H->next!=q){
	p=H;
	while(p->next!=q){
		if(p->No<p->next->No){
			if(p==H){
				H=p->next;
				p->next=H->next;
				H->next=p;
				r=H;
			}
			else {
				r->next=p->next;
				p->next=p->next->next;
				r->next->next=p;
				r=r->next;
			}
		}
		else{
			r=p;
			p=p->next;
		}
	}
	q=p;
}

printf("Sorted list: ");
p=H;
while(p!=NULL){
	printf("->%d", p->No);
	p=p->next;
}
printf("\n");

}