NP *multyXmulty( NP *ha, NP *hb ){ //实现两个多项式ha和hb的相乘, 返回结果多项式hc(链表头指针)

以下是一个基于链表的多项式乘法实现：

struct PolyNode {
    int coef;  // 系数
    int exp;   // 指数
    PolyNode* next;
    PolyNode(int c = 0, int e = 0, PolyNode* n = nullptr): coef(c), exp(e), next(n) {}
};

using NP = PolyNode*;

NP multyXmulty(NP ha, NP hb) {
    NP hc = new PolyNode();  // 初始化结果多项式头结点
    NP pc;                   // 结果多项式当前结点指针
    NP pa = ha, pb;          // 两个输入多项式的指针

    for (; pa != nullptr; pa = pa->next) {
        pb = hb;
        for (; pb != nullptr; pb = pb->next) {
            // 计算当前项的系数和指数
            int coef = pa->coef * pb->coef;
            int exp = pa->exp + pb->exp;

            // 在结果多项式中寻找当前项应该插入的位置
            pc = hc;
            while (pc->next != nullptr && pc->next->exp > exp) {
                pc = pc->next;
            }

            // 如果结果多项式中已经存在当前指数的项，则将其系数累加
            if (pc->next != nullptr && pc->next->exp == exp) {
                pc->next->coef += coef;
            } else {  // 否则插入一项新结点
                pc->next = new PolyNode(coef, exp, pc->next);
            }
        }
    }

    return hc;
}

该算法的时间复杂度为 $O(n^2)$，其中 $n$ 是多项式的最高次数。如果需要更高效的实现，可以考虑使用快速傅里叶变换（FFT）算法。