#include<iostream>
using namespace std;

typedef struct LinkNode
{
  int cofe;//系数
  int  exp;//次方
  struct LinkNode* next;
}LinkList,LinkNode;

//初始化链表
void initLinkList(LinkList*& L)
{ 
  L = new LinkList;
  L->next = NULL;
}
//尾插
void LinkPushBack(LinkList* L, int _cofe, int _exp)
{
  LinkNode* node = new LinkNode;
  node->cofe = _cofe;
  node->exp = _exp;

  LinkNode* temp = L;
  while (temp->next)
  {
    temp = temp->next;
  }
  temp->next = node;
  node->next = NULL;
}

//输入数据
void inputPoly(LinkList* L1, LinkList* L2)
{
  //系数，次方
  int l1cofe = 0;
  int l2cofe = 0;
  int l1exp = 0;
  int l2exp = 0;

  //几项式
  int l1num = 0;
  int l2num = 0;

  cout << "第一个多项式有几项?" << endl;
  cin >> l1num;
  for (int i = 0; i < l1num; i++)
  {
    cout << "请输入第"<<i+1<<"项的系数:" << endl;
    cin >> l1cofe;
    cout << "请输入第" << i+1 << "项的次方:" << endl;
    cin >> l1exp;
    LinkPushBack(L1, l1cofe, l1exp);
  }
  cout << "第一个多项式输入完毕!" << endl;

  cout << "第二个多项式有几项?" << endl;
  cin >> l2num;
  for (int i = 0; i < l2num; i++)
  {
    cout << "请输入第" << i+1<< "项的系数:" << endl;
    cin >> l2cofe;
    cout << "请输入第" << i+1 << "项的次方:" << endl;
    cin >> l2exp;
    LinkPushBack(L2, l2cofe, l2exp);
  }
  cout << "第二个多项式输入完毕！" << endl;
  cout << "多项式输入完毕!" << endl;
}

//多项式求和运算
void sumList(LinkList* L1, LinkList* L2)
{
  LinkNode* p = L1->next;//p为结果链表
  LinkNode* q = L2->next;
  LinkNode* pFront = L1;
  LinkNode* qFront = L2;
  //cofe系数
  //exp次方

  while (q && p)
  {
    if (p->exp == q->exp)//是同类项，可以合并，结果合并到p中
    {
      p->cofe += q->cofe;
      LinkNode* temp = new LinkNode;
      //删除q的结点
      temp = q;
      qFront->next = temp->next;
      delete temp;

      //工作指针后移
      pFront = p;
      p = p->next;

      q = qFront->next;
    }
    else if(p->exp < q->exp)//结果链表对应次方比q链表对应结点次方小，结果链表中工作指针后移
    {
      pFront = p;
      p = p->next;
    }
    else if(p->exp > q->exp)//结果链表对应次方比q链表对应结点次方大，q对应结点插过来。
    {
      //将这个结点插入到结果结点中

      qFront->next = q->next;
      pFront->next = q;
      q->next = p;
      
      q = qFront->next;//重新回到对应链表
      //结果链表的前指针后移
      pFront = pFront->next;
    }
  }
  //如果多项式L2的长度大于L1的，此时结束时，L2还有没遍历到的结点，次方大于L1所有的结点，直接插入到结果链表(L1)尾部
  if (q)//加个判断条件防止，L1最后一个项，系数大于L2的，也进入下面这个循环
  {
    while (q)
    {
      pFront->next = q;
      pFront = pFront->next;
      q = q->next;
    }
    pFront->next = NULL;//链接完成后尾结点next域置空
  }
  L2->next = NULL;//到达这里，L2除了head结点之外，后面的就算有内容也不属于它了。

  cout << "相加结果为:" << endl;
  L1 = L1->next;
  while (L1)
  {
    cout << "(" << L1->cofe << "," << L1->exp << ")" << " ";
    L1 = L1->next;
  } 
}
//销毁链表
void destoryLink(LinkNode*& L)
{
  LinkNode* tempNode = L;
  while (tempNode)
  {
    L = L->next;
    delete tempNode;
    tempNode = L;
  }
}
int main(void)
{
  LinkList* L1;
  LinkList* L2;
  initLinkList(L1);
  initLinkList(L2);
  
  inputPoly(L1, L2);
  sumList(L1, L2) ;

  destoryLink(L1);
  destoryLink(L2);

  return 0;
}