使用链表实现多项式相加

假设有两个多项式：

P1(x) = 3x^3 + 2x^2 + x + 5
P2(x) = 2x^3 - 1x^2 + 7x + 3

将多项式转化为链表形式，每个节点包含单项式的系数和指数。例如，第一个多项式可以表示为：

5 -> 1 -> 2 -> 3

每个节点的第一个元素表示系数，第二个元素表示指数。第一个节点表示常数项。

接下来使用以下步骤实现多项式相加：

1. 初始化两个指针分别指向两个多项式的头节点。

2. 创建一个新的链表用于存储结果。

3. 当两个指针都没有到达链表的末尾时，执行以下操作：

a. 如果当前指针指向的节点的指数相等，将两个节点的系数相加，并将结果插入到新链表中。

b. 如果当前指针指向的节点的指数不相等，则将指数较小的节点插入到新链表中，并将指向该节点的指针向后移动一位。

4. 当其中一个指针到达链表的末尾时，将另一个链表中剩余的节点依次插入到新链表中。

5. 返回新的链表，即为相加后的多项式。

以下是一个Python代码示例实现多项式相加：

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

def add_polynomials(p1, p2):
ptr1, ptr2 = p1, p2
head = Node(0, 0)
ptr = head

while ptr1 and ptr2:
if ptr1.exp == ptr2.exp:
coeff_sum = ptr1.coeff + ptr2.coeff
if coeff_sum != 0:
ptr.next = Node(coeff_sum, ptr1.exp)
ptr = ptr.next
ptr1 = ptr1.next
ptr2 = ptr2.next
elif ptr1.exp > ptr2.exp:
ptr.next = Node(ptr1.coeff, ptr1.exp)
ptr = ptr.next
ptr1 = ptr1.next
else:
ptr.next = Node(ptr2.coeff, ptr2.exp)
ptr = ptr.next
ptr2 = ptr2.next

while ptr1:
ptr.next = Node(ptr1.coeff, ptr1.exp)
ptr = ptr.next
ptr1 = ptr1.next

while ptr2:
ptr.next = Node(ptr2.coeff, ptr2.exp)
ptr = ptr.next
ptr2 = ptr2.next

return head.next

p1 = Node(5, 0, Node(1, 1, Node(2, 2, Node(3, 3))))
p2 = Node(3, 0, Node(7, 1, Node(-1, 2, Node(2, 3))))
p_sum = add_polynomials(p1, p2)

while p_sum:
print(p_sum.coeff, "x^", p_sum.exp, " + " if p_sum.next else "", end="")
p_sum = p_sum.next

# 输出：8 x^ 0 + 8 x^ 1 + 1 x^ 2 + 5 x^ 3