用链表结构存储多项式，求两个多项式A加B的和

假设多项式A和B的链表结构如下：

A: 3x^2 + 4x + 1
B: 2x^3 + 5x^2 + 2x + 3

我们可以先定义一个Node类来表示多项式中的每一项：

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

然后定义一个Polynomial类来表示整个多项式：

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

def insert(self, coeff, exp):
new_node = Node(coeff, exp)
if self.head is None:
self.head = new_node
else:
curr = self.head
while curr.next is not None:
curr = curr.next
curr.next = new_node

def __str__(self):
curr = self.head
result = ""
while curr is not None:
if curr.coeff == 0:
pass
elif curr.coeff == 1 and curr.exp == 0:
result += "1"
elif curr.coeff == -1 and curr.exp == 0:
result += "-1"
elif curr.coeff == 1 and curr.exp == 1:
result += "x"
elif curr.coeff == -1 and curr.exp == 1:
result += "-x"
elif curr.coeff == 1:
result += "x^" + str(curr.exp)
elif curr.coeff == -1:
result += "-x^" + str(curr.exp)
elif curr.exp == 0:
result += str(curr.coeff)
elif curr.exp == 1:
result += str(curr.coeff) + "x"
else:
result += str(curr.coeff) + "x^" + str(curr.exp)
if curr.next is not None and curr.next.coeff > 0:
result += " + "
elif curr.next is not None and curr.next.coeff < 0:
result += " - "
curr = curr.next
return result

现在可以用这个Polynomial类来表示上面的多项式A和B：

A = Polynomial()
A.insert(3, 2)
A.insert(4, 1)
A.insert(1, 0)

B = Polynomial()
B.insert(2, 3)
B.insert(5, 2)
B.insert(2, 1)
B.insert(3, 0)

最后，我们可以定义一个函数来计算A和B的和：

def add_polynomials(A, B):
result = Polynomial()
curr_A = A.head
curr_B = B.head

while curr_A is not None and curr_B is not None:
if curr_A.exp > curr_B.exp:
result.insert(curr_A.coeff, curr_A.exp)
curr_A = curr_A.next
elif curr_A.exp < curr_B.exp:
result.insert(curr_B.coeff, curr_B.exp)
curr_B = curr_B.next
else:
result.insert(curr_A.coeff + curr_B.coeff, curr_A.exp)
curr_A = curr_A.next
curr_B = curr_B.next

while curr_A is not None:
result.insert(curr_A.coeff, curr_A.exp)
curr_A = curr_A.next

while curr_B is not None:
result.insert(curr_B.coeff, curr_B.exp)
curr_B = curr_B.next

return result

现在我们可以调用这个函数来计算A和B的和：

C = add_polynomials(A, B)
print(C) # 输出结果为: "2x^3 + 8x^2 + 6x + 4"