用 Python 构建一个由两个具有一些公共节点的排序链表构成的最大和链表
假设我们有两个排序链表，我们必须创建一个由从起始节点到终止节点的最大和路径组成的链表。最终列表可能由两个输入列表中的节点组成。
当我们创建结果列表时，我们可能只针对交点(列表中具有相同值的两个节点)切换到另一个输入列表。我们必须使用恒定量的额外空间来解决它。
因此，如果输入为 [6,8,35,95,115,125]、[5,8,17,37,95,105,125,135]，则输出将为 [6,8,17,37,95,115,125,135]
要解决这个问题，我们将遵循以下步骤 −
result := None
previous1 := a, current1 := a
previous2 := b, current2 := b
当 current1 与 None 不同或 current2 与 None 不同时，执行
res1 := 0, res2 := 0
当 current1 和 current2 不为空且 current1 的数据与 current2 的数据不同时，执行
如果 current1 的数据 < current2 的数据，则
res1 := res1 + current1 的数据
current1 := current1 的下一个
否则，
res2 := res2 + current2 的数据
current2 := current2 的下一个
如果 current1 为空，则
当 current2 不为空时，执行
res2 := res2 + current2 的数据
current2 := next of current2
如果 current2 为空，则
当 current1 不为空时，执行
res1 := res1 + current1 的数据
current1 := current1 的下一个
如果 previous1 与 a 相同且 previous2 与 b 相同，则
result := previous1 when (res1 > res2) else previous2
否则，
如果 res1 > res2，然后
next of previous2 := next of previous1
否则，
next of previous1 := next of previous2
previous1 := current1
previous2 := current2
如果 current1 不为空，则
current1 := next of current1
如果 current2 不为空，则
current2 := next of current2
显示结果内容。
示例
让我们看看下面的实现以便更好地理解 −
class LinkedList(object): def __init__(self, data_set = []): self.head = None if len(data_set) > 0: for item in data_set: self.insert_node(item) class ListNode(object): def __init__(self, d): self.data = d self.next = None def insert_node(self, new_data): new_node = self.ListNode(new_data) new_node.next = self.head self.head = new_node def find_max_sum_list(self, a, b): result = None previous1 = a current1 = a previous2 = b current2 = b while current1 != None or current2 != None: res1 = 0 res2 = 0 while current1 != None and current2 != None and current1.data != current2.data: if current1.data < current2.data: res1 += current1.data current1 = current1.next else: res2 += current2.data current2 = current2.next if current1 == None: while current2 != None: res2 += current2.data current2 = current2.next if current2 == None: while current1 != None: res1 += current1.data current1 = current1.next if previous1 == a and previous2 == b: result = previous1 if (res1 > res2) else previous2 else: if res1 > res2: previous2.next = previous1.next else: previous1.next = previous2.next previous1 = current1 previous2 = current2 if current1 != None: current1 = current1.next if current2 != None: current2 = current2.next while result != None: print(result.data, end = ' ') result = result.next my_list1 = LinkedList([125,115,95,35,8,6]) my_list2 = LinkedList([135,125,105,95,37,17,8,5]) my_list1.find_max_sum_list(my_list1.head, my_list2.head)
输入
[125,115,95,35,8,6], [135,125,105,95,37,17,8,5]
输出
6 8 17 37 95 115 125 135
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
