#include <stdio.h>
#include <conio.h>
#include <alloc.h>
struct poly {
  int coef,x;
  struct poly *next;
} *p1start,*p1end;

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

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

}

void printp()
{
  struct poly *p;

  printf("the polymonial p1 --> f(x)="); p=p1start;
  while (p != NULL) {
    if (p->x != 0) printf("%dX(%d)",p->coef,p->x);
    else printf("%d\n",p->coef);
    p=p->next; if (p != NULL) printf("+");
  }
  printf("\n");
}

void main()
{

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

  while (1) { // the polynomial p1
    printf("give me the data coef and x --> "); scanf("%d %d",&coef,&x);
    if (coef == 0) break;
    if (fg == 0) {
       fg=1; p1start=p1end=p=(struct poly *)malloc(sizeof(struct poly));
    }
    else {
      p=(struct poly *)malloc(sizeof(struct poly));
      p1end->next=p; p1end=p;
    }
    p->next=NULL; p->coef=coef; p->x=x; if (x == 0) break;
  }
  printp(); printf("reverse the list -->\n");  reverse(); printp();
  printf("reverse the list -->\n");  reverse(); printp();

  printf("insert node into the polymonial -->\n");
  while (1) {
    printf("\ngive me the data coef and x --> "); scanf("%d %d",&coef,&x);
    if (coef == 0) break;
    ppre=p1start; pnext=ppre->next;
    if (x >= p1start->x) {  // insert into head
      if (x > p1start->x) {
	p=(struct poly *)malloc(sizeof(struct poly));
	p->coef=coef; p->x=x; p->next=p1start; p1start=p;
      }
      else { // equal in the head
	ppre->coef=ppre->coef+coef;
	if (ppre->coef == 0) ppre=p1start=ppre->next;
      }
    }
    else {  // x <= p1start->x
       fg=0;
       while (pnext->x > x) {
	  ppre=pnext; pnext=pnext->next;
	  if (pnext == NULL) { // insert into the end
	    p=(struct poly *)malloc(sizeof(struct poly)); p->coef=coef;
	    p->x=x; ppre->next=p; p->next=NULL; fg=1; break;
	  }// if
       } // while
       if (fg == 0)
	 if (pnext->x == x) {
	   pnext->coef=pnext->coef+coef;
	   if (pnext->coef == 0) ppre->next=pnext->next;
	 } // if
	 else {
	   p=(struct poly *)malloc(sizeof(struct poly)); p->coef=coef;
	   p->x=x; p->next=ppre->next; ppre->next=p;
	 }
    } // else
  } // while
  printp();
}