基于链表的两个一元多项式的基本运算

链表可以用来表示一元多项式，每个节点代表一个项，包含系数和指数。基本运算包括加法、减法和乘法。

加法和减法的思路都很类似，都是将链表中对应指数的项相加或相减。具体实现时，可以先将两个链表按指数从小到大排序，然后同时遍历两个链表，按照指数大小比较，将对应项相加或相减，生成新的节点插入结果链表中。如果某一链表已经遍历结束，则将另一链表的剩余项直接插入结果链表中。

乘法的实现稍微复杂一些。可以采用两个循环嵌套的方式，分别遍历两个链表，将每个项相乘得到新的项，并将新的项插入结果链表中。具体实现时，需要注意项之间的系数和指数相乘的规律，以及结果链表中相同指数的项需要合并的问题。可以使用一个哈希表来记录每个指数在结果链表中的位置，然后在插入新项时，根据指数查找哈希表，判断是否有相同指数的项存在，如果存在，则将系数相加，否则新建一个节点并插入结果链表中，并更新哈希表中的指数位置信息。

下面是 C++ 实现示例：

#include <iostream>
#include <unordered_map>

using namespace std;

struct Node {
    int coef;
    int exp;
    Node *next;
    Node(int coef_, int exp_) : coef(coef_), exp(exp_), next(nullptr) {}
};

void insert(Node *&head, int coef, int exp) {
    Node *node = new Node(coef, exp);
    if (head == nullptr || head->exp < exp) {
        node->next = head;
        head = node;
    } else {
        Node *prev = nullptr, *curr = head;
        while (curr != nullptr && curr->exp > exp) {
            prev = curr;
            curr = curr->next;
        }
        if (curr != nullptr && curr->exp == exp) {
            curr->coef += coef;
            if (curr->coef == 0) {
                if (prev == nullptr) {
                    head = curr->next;
                } else {
                    prev->next = curr->next;
                }
                delete curr;
            }
        } else {
            node->next = curr;
            prev->next = node;
        }
    }
}

Node *add(Node *p1, Node *p2) {
    Node *head = nullptr;
    while (p1 != nullptr && p2 != nullptr) {
        if (p1->exp == p2->exp) {
            insert(head, p1->coef + p2->coef, p1->exp);
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->exp > p2->exp) {
            insert(head, p1->coef, p1->exp);
            p1 = p1->next;
        } else {
            insert(head, p2->coef, p2->exp);
            p2 = p2->next;
        }
    }
    while (p1 != nullptr) {
        insert(head, p1->coef, p1->exp);
        p1 = p1->next;
    }
    while (p2 != nullptr) {
        insert(head, p2->coef, p2->exp);
        p2 = p2->next;
    }
    return head;
}

Node *subtract(Node *p1, Node *p2) {
    Node *head = nullptr;
    while (p1 != nullptr && p2 != nullptr) {
        if (p1->exp == p2->exp) {
            insert(head, p1->coef - p2->coef, p1->exp);
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->exp > p2->exp) {
            insert(head, p1->coef, p1->exp);
            p1 = p1->next;
        } else {
            insert(head, -p2->coef, p2->exp);
            p2 = p2->next;
        }
    }
    while (p1 != nullptr) {
        insert(head, p1->coef, p1->exp);
        p1 = p1->next;
    }
    while (p2 != nullptr) {
        insert(head, -p2->coef, p2->exp);
        p2 = p2->next;
    }
    return head;
}

Node *multiply(Node *p1, Node *p2) {
    Node *head = nullptr;
    unordered_map<int, Node *> m;
    for (; p1 != nullptr; p1 = p1->next) {
        for (Node *p = p2; p != nullptr; p = p->next) {
            int coef = p1->coef * p->coef;
            int exp = p1->exp + p->exp;
            if (m.count(exp) == 0) {
                m[exp] = new Node(coef, exp);
            } else {
                insert(m[exp], coef, exp);
            }
        }
    }
    for (auto &item : m) {
        if (item.second->coef != 0) {
            insert(head, item.second->coef, item.second->exp);
        }
    }
    return head;
}

void print(Node *head) {
    if (head == nullptr) {
        cout << "0" << endl;
    } else {
        while (head != nullptr) {
            cout << head->coef << "x^" << head->exp;
            head = head->next;
            if (head != nullptr) {
                cout << " + ";
            }
        }
        cout << endl;
    }
}

int main() {
    Node *p1 = nullptr, *p2 = nullptr;
    insert(p1, 2, 3);
    insert(p1, 4, 1);
    insert(p1, 3, 0);
    insert(p2, 3, 4);
    insert(p2, 1, 3);
    insert(p2, 2, 1);
    print(add(p1, p2));        // 3x^4 + 2x^3 + 2x^1 + 3
    print(subtract(p1, p2));   // -3x^4 + 2x^3 + 2x^1 - 3
    print(multiply(p1, p2));   // 6x^7 + 14x^5 + 13x^4 + 10x^3 + 9x^1 + 6
    return 0;
}