用python语言利用单链表实现多项式相加

在Python中，可以使用链表数据结构来实现多项式的相加，因为链表非常适合表示有序的数据序列，每个节点通常包含一个系数和一个变量指数。这里我们可以创建两个链表，分别代表两个多项式，然后遍历这两个链表，将相应的项相加。

首先，定义一个链表节点的类，包含系数和指数：

class Node:
    def __init__(self, coef=0, exp=0):
        self.coef = coef
        self.exp = exp
        self.next = None

class PolynomialList:
    def __init__(self):
        self.head = None

接着，我们有函数来进行多项式的加法：

def add_poly_list(poly1, poly2):
    # 创建一个新的空链表作为结果
    result = PolynomialList()
    current = result.head = Node()

    # 分别处理两个链表的头节点
    while poly1 and poly2:
        # 对应系数相加
        if poly1.head.exp == poly2.head.exp:
            sum_coef = poly1.head.coef + poly2.head.coef
            # 如果和为零，则删除当前项
            if not sum_coef:
                if poly1.head == poly1.head.next:
                    poly1.head = poly1.head.next
                elif poly2.head == poly2.head.next:
                    poly2.head = poly2.head.next
                else:
                    current.next = poly1.head.next
                    poly1.head = poly1.head.next
                    current = current.next
            else:
                # 更新当前节点和下一个节点
                current.next = Node(sum_coef)
                current = current.next
                poly1.head = poly1.head.next
                poly2.head = poly2.head.next
        # 移动到下一项
        elif poly1.head.exp < poly2.head.exp:
            current.next = poly1.head
            poly1.head = poly1.head.next
        else:
            current.next = poly2.head
            poly2.head = poly2.head.next

    # 将剩余的链表添加到结果
    while poly1:
        current.next = poly1.head
        poly1.head = poly1.head.next
        current = current.next
    while poly2:
        current.next = poly2.head
        poly2.head = poly2.head.next
        current = current.next

    return result

现在你可以使用这个`add_poly_list`函数来合并两个多项式链表了。例如：

poly1 = PolynomialList()
poly1.head = Node(1, 2)  # 1x^2
poly1.head.next = Node(3, 1)  # 3x^1

poly2 = PolynomialList()
poly2.head = Node(4, 0)   # 4x^0 (常数项)
poly2.head.next = Node(-2, 1)  # -2x^1

result = add_poly_list(poly1, poly2)