#include <stdio.h>
#include <conio.h>
#include <alloc.h>
struct poly {
  int x;
  struct poly *pre,*next;
} *start;

void reverse()
{
  struct poly *p,*ppre,*pnext;

  ppre=start; pnext=ppre->next; p=NULL;
  while (pnext != NULL) {
    ppre->next=p; p=ppre; ppre=pnext; pnext=pnext->next;
  }
  ppre->next=p; start=ppre;
}

void printp()
{
  struct poly *p;

  printf("the input value is --> "); p=start;
  while (p != NULL) {
    printf("%d ",p->x); p=p->next;
  }
  printf("\n");
}

void main()
{

  int x,fg=0,ff=0;
  struct poly *p,*ppre,*pnext;

  while (1) { /* the polynomial p1 */
    printf("give me the data --> "); scanf("%d",&x);
    if (x == 0) break;
    if (ff == 0) { /* 1st item */
       ff=1; start=p=(struct poly *)malloc(sizeof(struct poly));
       p->x=x; p->next=NULL; continue;
    }
    else {
      ppre=start; pnext=ppre->next;
      if (x >= start->x) {  /* insert into head */
	if (x > start->x) {
	  p=(struct poly *)malloc(sizeof(struct poly));
	  p->x=x; p->next=start; start=p;
	}
        else printf("data duplicated!!!\n");
      }
      else {  /* x < start->x */
	fg=0;
        if (pnext != NULL) {
          while (pnext->x >= x) {
            if (pnext->x == x) printf("data duplicated!!!\n");
            else {
              ppre=pnext; pnext=pnext->next;
              if (pnext == NULL) { /* insert into the end */
                p=(struct poly *)malloc(sizeof(struct poly)); p->x=x;
                ppre->next=p; p->next=NULL; fg=1; break;
              }/* if */
            }
          } /* while */
        }
	if (fg == 0) {
	   p=(struct poly *)malloc(sizeof(struct poly)); p->x=x;
	   p->next=ppre->next; ppre->next=p;
	}
      } /* else x < start-> x */
    } /* else not the 1st item */
  } /* while */
  printp(); reverse(); printp();
}