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

void printp(struct poly *start)
{
  struct poly *p;

  printf("the input value is --> "); p=start;
  while (p != NULL) {
    printf("%dX^%d ",p->coef,p->power); p=p->next;
    if (p!=NULL) printf("+ "); else printf("\n");
  }
}

struct poly * create()
{
  int x1,x2,fg=0,ff=0;
  struct poly *p,*ppre,*pnext;

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

void main()
{
  struct poly *h1, *h2, *p1,*p2, *h3, *p3, *pp;
  int ff=0,tt;

  p1=h1=create(); printp(h1); p2=h2=create(); printp(h2);
  p3=h3=(struct poly *)malloc(sizeof(struct poly));
  while ((p1 != NULL) && (p2 != NULL)) {
    if (p1->power > p2->power) {
      if (ff == 0) { h3->power=p1->power; h3->coef=p1->coef; ff=1; }
      else {
        pp=(struct poly *)malloc(sizeof(struct poly)); pp->power=p1->power;
        pp->coef=p1->coef; pp->next=NULL; p3=p3->next=pp;
      }
      p1=p1->next;
    }
    if (p1->power < p2->power) {
      if (ff == 0) { h3->power=p2->power; h3->coef=p2->coef; ff=1; }
      else {
        pp=(struct poly *)malloc(sizeof(struct poly)); pp->power=p2->power;
        pp->coef=p2->coef; pp->next=NULL; p3=p3->next=pp;
      }
      p2=p2->next;
    }
    else { /* p1->power = p2->power */
      tt=p1->coef+p2->coef;
      if (tt != 0) {
        if (ff == 0) { h3->power=p1->power; h3->coef=tt; ff=1; }
        else {
          pp=(struct poly *)malloc(sizeof(struct poly)); pp->power=p2->power;
          pp->coef=tt; pp->next=NULL; p3=p3->next=pp;
        }
      }
      p2=p2->next; p1=p1->next; 
    } /* else */
  } /* while */
  if (p1 == NULL) 
    while (p2 != NULL) {
      pp=(struct poly *)malloc(sizeof(struct poly)); pp->power=p2->power;
      pp->coef=p2->coef; pp->next=NULL; p3=p3->next=pp; p2=p2->next;
    }
  else if (p2 == NULL) 
    while (p1 != NULL) {
      pp=(struct poly *)malloc(sizeof(struct poly)); pp->power=p1->power;
      pp->coef=p1->coef; pp->next=NULL; p3=p3->next=pp; p1=p1->next;
    }
  printp(h3);
}