数据结构用链表实现多项式相加

假设我们有两个多项式：P1 = 2x^3 + 3x^2 + 4x + 5 和 P2 = 3x^2 + 4x + 5

我们可以用链表来表示这两个多项式。每个节点包含两个值：系数和指数。我们可以将它们存储在一个结构体中：

struct Node {
    int coeff; // 系数
    int exp; // 指数
    Node* next; // 指向下一个节点的指针
};

然后，我们可以创建两个链表，一个表示P1，一个表示P2。链表应该按照指数的降序排列，这样我们可以更容易地进行相加。下面是一个示例链表：

P1: 2x^3 -> 3x^2 -> 4x -> 5
P2: 3x^2 -> 4x -> 5

为了相加这两个多项式，我们需要遍历它们的链表，并将它们的项相加。具体来说，我们可以按照以下方式进行：

1. 初始化结果链表为空。
2. 从头开始遍历P1和P2的链表。
3. 如果P1的当前项的指数大于P2的当前项的指数，则将P1的当前项添加到结果链表中，然后将P1的指针向前移动一个节点。
4. 如果P2的当前项的指数大于P1的当前项的指数，则将P2的当前项添加到结果链表中，然后将P2的指针向前移动一个节点。
5. 如果P1和P2的当前项的指数相等，则将它们的系数相加，并将结果添加到结果链表中。然后将P1和P2的指针都向前移动一个节点。
6. 当P1和P2的链表都遍历完时，结束循环。

下面是一个用C++实现的示例代码：

Node* addPolynomials(Node* p1, Node* p2) {
    Node* result = nullptr; // 结果链表的头指针
    Node** pp = &result; // 指向结果链表的尾指针的指针

    while (p1 != nullptr || p2 != nullptr) {
        if (p1 == nullptr || (p2 != nullptr && p1->exp < p2->exp)) {
            *pp = new Node{ p2->coeff, p2->exp, nullptr };
            p2 = p2->next;
        }
        else if (p2 == nullptr || (p1 != nullptr && p1->exp > p2->exp)) {
            *pp = new Node{ p1->coeff, p1->exp, nullptr };
            p1 = p1->next;
        }
        else {
            *pp = new Node{ p1->coeff + p2->coeff, p1->exp, nullptr };
            p1 = p1->next;
            p2 = p2->next;
        }
        pp = &((*pp)->next);
    }

    return result;
}

这个函数接受两个指向链表头节点的指针，然后返回一个指向结果链表头节点的指针。我们使用了一个指向结果链表尾节点的指针的指针，这样我们可以更方便地将新节点添加到结果链表的末尾。