.链表实现两个一元多项式的加法代码
时间: 2024-09-24 08:04:40 浏览: 9
链表可以用于存储一元多项式,其中每个节点代表一个系数和对应的变量幂次。要实现两个一元多项式的加法,你需要创建一个新的链表,将两个输入链表的对应项相加,并更新新链表。这里是一个简单的Python示例:
```python
class ListNode:
def __init__(self, coefficient=0, power=0):
self.coefficient = coefficient
self.power = power
self.next = None
def add_polynomials(lst1, lst2):
dummy_head = ListNode(0) # 创建虚拟头节点
current = dummy_head # 当前节点指向dummy_head
while lst1 and lst2:
sum_coefficient = lst1.coefficient + lst2.coefficient
if lst1.power > lst2.power:
current.next = ListNode(sum_coefficient, lst1.power)
lst1 = lst1.next
elif lst2.power > lst1.power:
current.next = ListNode(sum_coefficient, lst2.power)
lst2 = lst2.next
else:
current.next = ListNode(sum_coefficient, lst1.power)
lst1 = lst1.next
lst2 = lst2.next
if lst1 is not None:
current.next = lst1
elif lst2 is not None:
current.next = lst2
return dummy_head.next # 返回新链表的头节点
# 示例:
lst1 = ListNode(2, 1), ListNode(3, 0) # 2x^1 + 3x^0
lst2 = ListNode(1, 2), ListNode(4, 1) # 1x^2 + 4x^1
result = add_polynomials(lst1, lst2) # 结果链表:(5, 1)(7, 2)
```
在这个例子中,我们遍历两个链表,逐项相加并构建新的链表。注意,如果有一个链表比另一个长,我们会将剩余的部分添加到结果链表的末尾。