#include <stdio.h>

/*構造体の定義*/
struct Cell 
{
	int number;
	struct Cell *next;
};

/*プロトタイプ宣言*/
void p_list(struct Cell *topcell_ptr);

int main(void)
{

	/*変数の定義*/
	int n;	/*入力された数字を受けるための変数*/

	/*rootの定義*/
	struct Cell *root;

	/*新しいセルを指すポインタの定義*/
	struct Cell *newcell_ptr;

	/*今注目している２つのセルのうち、小さいほうのセルを指すポインタの定義*/
	struct Cell *smallcell_ptr;

	/*今注目している２つのセルのうち、大きいほうのセルを指すポインタの定義*/
	struct Cell *bigcell_ptr;

	/*rootはとりあえずNULLを指す*/
	root=NULL; 
	

	/*プログラムの説明*/
	printf("整数をいくつか入力してください。\n0が入力されると終了します。\n");

	while(1){	/*無限ループ*/
		
		/*値の入力*/
		scanf("%d",&n);

		if(n==0)break; /*0が入力されたらループ脱出*/

		/*構造体変数とポインタの作成*/
		newcell_ptr=(struct Cell*)malloc(sizeof(struct Cell));

		/*新しくできた構造体変数内のint型変数に、
		入力された値を代入する*/
		newcell_ptr->number=n;


		/*ポインタの操作*/
	
		if(root==NULL){
		/*rootがNULLの時(つまり初回)は、rootとnewcell_ptr->nextの値を入れ替える*/
			root=newcell_ptr;
			newcell_ptr->next=NULL;
			
			}

		else{	/*初回以外のとき*/
		
			if (root->number>=newcell_ptr->number){	 /*最新セルのnumberの値が最小のとき*/
				
				/*最新セル内のポインタに、今までrootが指していたとこを指させる*/
				newcell_ptr->next=root;
				
				/*rootは最新セル（つまり最小セル）を指す*/
				root=newcell_ptr;
				
				}

			else{	 /*最新セルのnumberの値が最小でないとき*/
					
				/*まずsmallcell_ptrが１番目のセルを指すようにセット*/
				smallcell_ptr=root;
				
				/*次に、bigcell_ptrがsmallcell_ptrの次のセルを指すようにセット*/
				bigcell_ptr=smallcell_ptr->next;
				
				while(1){	/*無限ループ*/
					

					
					if (bigcell_ptr==NULL){
					/*最新セルの値が最大だった
					(つまりsmallcell_ptrの次が存在しない→bigcell_ptrがNULL)
					のときの処理*/
					
						/*small_ptrのセルが最新のセルを指すようにする*/
						smallcell_ptr->next=newcell_ptr;
						
						/*最新のセル内のポインタがNULLを指すようにする*/
						newcell_ptr->next=NULL;
						
						break;	/*ループ脱出*/
						}
						
					else { 
					/*bigcell_ptrがちゃんとセルを指してる(最後じゃない)時の処理*/
					
					

						
						if(bigcell_ptr->number>newcell_ptr->number){
						/*bigcell_ptrセル内のnumber値と、最新セル内のnumber値を
						比較して、bigcell_ptrセル内の方が大きかったとき
						つまり以下の式が成り立つとき
						(smallcell_ptr->number) < (newcell_ptr->number) < (bigcell_ptr->number)
						*/
						
						
						/*small_ptrのセルが最新のセルを指すようにする*/
						smallcell_ptr->next=newcell_ptr;
						
						/*最新のセル内のポインタがbigcell_ptrを指すようにする*/
						newcell_ptr->next=bigcell_ptr;
						
						break;	/*ループ脱出*/
						}



						else {
						/* (bigcell_ptr->number) < (newcell_ptr->number)  の時*/
						
						/*まずsmallcell_ptrがbigcell_ptrのセルを指すようにセット*/
						smallcell_ptr=bigcell_ptr;
						/*次に、bigcell_ptrがsmallcell_ptrの次のセルを指すようにセット*/
						bigcell_ptr=smallcell_ptr->next;
						}
						
					}/*bigcell_ptrが最後じゃなかったときの分岐を閉じてる*/
					
				}/*奥の無限ループ閉じてる*/
				
			}/*最新が最小値以外のときの分岐を閉じてる*/
			
		}	/*初回以外のときの分岐を閉じてる*/
		
	}	/*手前の無限ループを閉じてる*/
	
	/*線型リストの出力*/
	p_list(root);
	
        return 0;
        
}	/*mainを閉じてる*/


/*線型リストを先頭から順に画面に印字する*/
void p_list(struct Cell *topcell_ptr)
{

	while(topcell_ptr!=NULL){
		printf("%d  ", topcell_ptr->number);
		topcell_ptr= topcell_ptr->next;
		}
}