难度: Medium
Submission
运行时间: 309 ms
内存: 25.1 MB
# Definition for polynomial singly-linked list.
# class PolyNode:
# def __init__(self, x=0, y=0, next=None):
# self.coefficient = x
# self.power = y
# self.next = next
class Solution:
def addPoly(self, poly1: 'PolyNode', poly2: 'PolyNode') -> 'PolyNode':
dummy = PolyNode() # 创建一个虚拟头节点
current = dummy # 当前节点指针
while poly1 and poly2:
if poly1.power == poly2.power:
coeff = poly1.coefficient + poly2.coefficient # 相同指数，系数相加
if coeff != 0: # 系数不为0，则创建新节点
current.next = PolyNode(coeff, poly1.power)
current = current.next
poly1 = poly1.next
poly2 = poly2.next
elif poly1.power > poly2.power:
current.next = PolyNode(poly1.coefficient, poly1.power) # 指数较大，直接创建新节点
current = current.next
poly1 = poly1.next
else:
current.next = PolyNode(poly2.coefficient, poly2.power) # 指数较小，直接创建新节点
current = current.next
poly2 = poly2.next
# 处理剩余节点
while poly1:
current.next = PolyNode(poly1.coefficient, poly1.power)
current = current.next
poly1 = poly1.next
while poly2:
current.next = PolyNode(poly2.coefficient, poly2.power)
current = current.next
poly2 = poly2.next
return dummy.next # 返回虚拟头节点的下一个节点作为结果多项式的头节点
Explain
这个题解采用了一个类似于合并两个有序链表的方法。首先创建一个虚拟头节点作为返回结果的基础。然后使用两个指针分别遍历两个多项式链表。对于每一对当前节点，比较它们的指数（power）。如果指数相同，则将它们的系数（coefficient）相加，并只在系数非零时添加到结果链表中；如果一个链表的当前节点的指数更大，则将该节点添加到结果链表中，并移动相应的指针。当一个链表遍历完毕后，将另一个链表的剩余部分直接链接到结果链表的尾部。这样就可以得到两个多项式的和。
时间复杂度: O(m+n)
空间复杂度: O(m+n)
# Definition for polynomial singly-linked list.
# class PolyNode:
# def __init__(self, x=0, y=0, next=None):
# self.coefficient = x
# self.power = y
# self.next = next
class Solution:
def addPoly(self, poly1: 'PolyNode', poly2: 'PolyNode') -> 'PolyNode':
dummy = PolyNode() # 创建一个虚拟头节点
current = dummy # 当前节点指针
while poly1 and poly2:
if poly1.power == poly2.power:
coeff = poly1.coefficient + poly2.coefficient # 相同指数，系数相加
if coeff != 0: # 系数不为0，则创建新节点
current.next = PolyNode(coeff, poly1.power)
current = current.next
poly1 = poly1.next
poly2 = poly2.next
elif poly1.power > poly2.power:
current.next = PolyNode(poly1.coefficient, poly1.power) # 指数较大，直接创建新节点
current = current.next
poly1 = poly1.next
else:
current.next = PolyNode(poly2.coefficient, poly2.power) # 指数较小，直接创建新节点
current = current.next
poly2 = poly2.next
# 处理剩余节点
while poly1:
current.next = PolyNode(poly1.coefficient, poly1.power)
current = current.next
poly1 = poly1.next
while poly2:
current.next = PolyNode(poly2.coefficient, poly2.power)
current = current.next
poly2 = poly2.next
return dummy.next # 返回虚拟头节点的下一个节点作为结果多项式的头节点
Explore
在多项式的运算中，具有相同指数的项被视为同类项。对同类项进行计算时，需要将系数相加以简化多项式的表示。创建两个单独的节点会导致相同指数的项分散在链表中，这不仅增加了处理的复杂度，还与多项式的标准简化形式相悖。因此，将系数相加是为了保持多项式的简洁和规范性。
在算法实现中，通过比较两个节点的指数来决定节点的插入顺序。如果一个节点的指数高于另一个，那么它会先被添加到结果链表中，从而保证了多项式的指数是按降序排列的。这种方式确保了即使在合并过程中，结果多项式的节点也总是保持正确的顺序。
如果输入中的一个或两个多项式链表为空，算法会直接将非空的多项式链表的剩余部分链接到结果链表的尾部。如果两个链表都为空，则结果链表也为空。这种处理方式确保了算法的鲁棒性和正确处理边界情况的能力。
在实现中，当将一个多项式链表的剩余部分直接链接到结果链表时，通常不需要对每个节点的系数是否为零进行额外检查。这是因为在主循环中已处理了系数为零的情形（通过将相同指数的系数相加并检查结果），因此剩余部分中的系数理应非零。然而，根据具体情况和多项式链表的来源，如果有可能出现系数为零的节点，则应添加检查以避免添加无效节点。