使用链表实现多项式加法与乘法

1. 引言

在数学中，多项式是由一个或多个变量的幂次组合而成的表达式，每个项由变量的幂次和一个系数相乘构成。例如：
a₀ + a₁x + a₂x² + ... + aₙxⁿ，其中每一项如 aₙxⁿ 被称为一个“项”（term）。如果两个项的幂次相同，我们称它们为“同类项”。

本教程中，我们将展示如何使用链表（Linked List）数据结构来表示多项式，并实现两个多项式的加法与乘法操作。

2. 使用链表表示多项式

我们可以使用链表来表示多项式，其中每个节点包含两个字段：系数（coefficient）和幂次（power）。每个节点代表多项式中的一个项。

例如，多项式 2 - 4x + 5x² 可以用如下链表表示：

polynomial

为了简化后续操作，我们假设链表中的节点是按照幂次降序排列的。如果链表不是有序的，可以使用归并排序算法在 O(n log n) 时间内完成排序。

3. 多项式加法

加法的核心在于合并同类项。例如：

多项式 A: 2 - 4x + 5x²
多项式 B: 1 + 2x - 3x³

它们的和为：3 - 2x + 5x² - 3x³

对应的链表为：

sum result

我们使用双指针法来合并两个有序链表，类似于合并两个有序链表的操作：

algorithm PolynomialAdd(head1, head2):
    // INPUT
    //    head1 = 第一个多项式链表头节点
    //    head2 = 第二个多项式链表头节点
    // OUTPUT
    //    新链表头节点，表示两个多项式的和
    head <- tail <- null
    p1 <- head1
    p2 <- head2
    while p1 != null and p2 != null: 
        if p1.power > p2.power:
            tail <- append(tail, p1.power, p1.coefficient)
            p1 <- p1.next
        else if p2.power > p1.power:
            tail <- append(tail, p2.power, p2.coefficient)
            p2 <- p2.next
        else:
            coefficient <- p1.coefficient + p2.coefficient
            if coefficient != 0:
                tail <- append(tail, p1.power, coefficient)
            p1 <- p1.next
            p2 <- p2.next
        if head is null:
            head <- tail
    while p1 != null:
        tail <- append(tail, p1.power, p1.coefficient)
        p1 <- p1.next
    while p2 != null:
        tail <- append(tail, p2.power, p2.coefficient)
        p2 <- p2.next
    return head

✅ 加法逻辑总结：

如果 p1.power > p2.power，则将 p1 节点添加到结果链表；
如果 p2.power > p1.power，则将 p2 节点添加到结果链表；
如果幂次相同，则合并系数，若系数和为 0 则跳过；
最后处理剩余节点。

时间复杂度为 O(n + m)，其中 n 和 m 分别为两个多项式的项数。

4. 多项式乘法

乘法操作的核心是将第一个多项式的每一项分别乘以第二个多项式的每一项，然后合并同类项。

例如：

多项式 A: 2 - 4x + 5x²
多项式 B: 1 + 2x - 3x³

它们的乘积展开后为：

2*1 = 2
2*2x = 4x
2*(-3x³) = -6x³
-4x*1 = -4x
-4x*2x = -8x²
-4x*(-3x³) = 12x⁴
5x²*1 = 5x²
5x²*2x = 10x³
5x²*(-3x³) = -15x⁵

合并后结果为：2 + (4x - 4x) + (-8x² + 5x²) + (-6x³ + 10x³) + 12x⁴ - 15x⁵ = 2 - 3x² + 4x³ + 12x⁴ - 15x⁵

对应的链表为：

multiply result

✅ 实现步骤如下：

两层循环遍历所有项对，生成所有乘积项；
对生成的链表进行按幂次排序；
合并同类项。

✅ 示例代码：

algorithm PolynomialMultiply(head1, head2):
    // INPUT
    //    head1 = 第一个多项式链表头节点
    //    head2 = 第二个多项式链表头节点
    // OUTPUT
    //    新链表头节点，表示两个多项式的乘积
    head <- null
    tail <- null
    p1 <- head1
    while p1 != null:
        p2 <- head2
        while p2 != null:
            power <- p1.power + p2.power
            coefficient <- p1.coefficient * p2.coefficient
            tail <- append(tail, power, coefficient)
            if head is null:
                head <- tail
            p2 <- p2.next
        p1 <- p1.next
    head <- mergesort(head)
    mergeLikeTerms(head)
    return head

✅ 合并同类项算法：

algorithm MergeLikeTerms(head):
    prev <- null
    p1 <- head
    while p1 != null:
        p2 <- p1.next
        while p2 != null and p2.power = p1.power:
            p1.coefficient <- p1.coefficient + p2.coefficient
            p2 <- p2.next
            p1.next <- p2
        if p1.coefficient = 0 and prev != null:
            prev.next <- p2
        else:
            prev <- p1
        p1 <- p2

⏱️ 时间复杂度分析：

生成所有乘积项：O(n * m)
排序：O(nm log(nm))
合并同类项：O(nm)

总时间复杂度为：O(nm log(nm))

5. 总结

本文介绍了如何使用链表来表示多项式，并实现了两个核心操作：

加法：使用双指针合并两个有序链表，时间复杂度为 O(n + m)
乘法：通过遍历所有项对生成乘积项，排序后合并同类项，总时间复杂度为 O(nm log(nm))

✅ 小贴士：

在链表操作中，注意指针的移动和节点的插入顺序，避免空指针异常；
对于乘法操作，排序是关键，否则合并同类项会非常低效；
若系数为 0，应跳过添加节点，避免冗余数据。

✅ 示例图解：

加法前两个多项式链表：
加法后结果：
乘法后未排序的中间链表：
排序后：
最终合并同类项结果：

✅ 完整代码可在实际项目中封装为类和方法，便于复用与维护。

Persistence

REST

Security