用C语言代码实现从标准输入中读入两个多项式。且该多项式中各项的系数均为0或正整数，最高幂次不超过1000000。对于多项式 anxn + an-1xn-1+.... + a1x1 + a0x0 （n<=1000000）的表示方法如下： an n an-1 n-1 ... a1 1 a0 0 第一、二行读入第一个多项式。第一行，表示多项式的项数。紧接着下一行输入该多项式的每一项。相邻两个整数分别表示表达式中一项的系数和指数。在输入中只出现系数不为0的项。 第三、四行读入第二个多项式。将运算结果输出到屏幕。将系数不为0的项按指数从高到低的顺序输出，每次输出其系数和指数，均以一个空格分隔。在行的末尾也输出一个空格符，并且最后要求换行。使用链表并且空间复杂度为O(1)

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int coef;  // 系数
    int exp;  // 指数
    struct Node *next;
} Node, *Polynomial;

Polynomial create() {  // 创建空链表
    Polynomial p = (Polynomial)malloc(sizeof(Node));
    p->next = NULL;
    return p;
}

Polynomial read() {  // 读入多项式
    int n, coef, exp;
    Polynomial p = create();
    scanf("%d", &n);
    while (n--) {
        scanf("%d %d", &coef, &exp);
        Polynomial q = (Polynomial)malloc(sizeof(Node));
        q->coef = coef;
        q->exp = exp;
        q->next = NULL;
        Polynomial t = p;
        while (t->next && t->next->exp > exp) {
            t = t->next;
        }
        if (t->next && t->next->exp == exp) {
            t->next->coef += coef;
            free(q);
        } else {
            q->next = t->next;
            t->next = q;
        }
    }
    return p;
}

void print(Polynomial p) {  // 输出多项式
    int flag = 0;
    while (p->next) {
        if (flag) {
            printf(" ");
        } else {
            flag = 1;
        }
        printf("%d %d", p->next->coef, p->next->exp);
        p = p->next;
    }
    printf("\n");
}

Polynomial add(Polynomial p1, Polynomial p2) {  // 多项式相加
    Polynomial p = create();
    Polynomial t = p;
    while (p1->next && p2->next) {
        if (p1->next->exp > p2->next->exp) {
            t->next = p1->next;
            p1 = p1->next;
        } else if (p1->next->exp < p2->next->exp) {
            t->next = p2->next;
            p2 = p2->next;
        } else {
            int coef = p1->next->coef + p2->next->coef;
            if (coef) {
                Polynomial q = (Polynomial)malloc(sizeof(Node));
                q->coef = coef;
                q->exp = p1->next->exp;
                q->next = NULL;
                t->next = q;
                p1 = p1->next;
                p2 = p2->next;
            } else {
                p1 = p1->next;
                p2 = p2->next;
            }
        }
        t = t->next;
    }
    if (p1->next) {
        t->next = p1->next;
    }
    if (p2->next) {
        t->next = p2->next;
    }
    return p;
}

int main() {
    Polynomial p1 = read();
    Polynomial p2 = read();
    Polynomial p = add(p1, p2);
    print(p);
    return 0;
}