数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学构建一个最大和链表，该链表由两个包含一些公共节点的有序链表构成 (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 不为 null 且 current1 的数据与 current2 的数据不相同时，执行以下操作：
如果 current1 的数据 < current2 的数据，则：
res1 := res1 + current1 的数据
current1 := current1 的下一个节点
否则：
res2 := res2 + current2 的数据
current2 := current2 的下一个节点
如果 current1 为 null，则：
当 current2 不为 null 时，执行以下操作：
res2 := res2 + current2 的数据
current2 := current2 的下一个节点
如果 current2 为 null，则：
当 current1 不为 null 时，执行以下操作：
res1 := res1 + current1 的数据
current1 := current1 的下一个节点
如果 previous1 等于 a 且 previous2 等于 b，则：
result := 如果 (res1 > res2) 则为 previous1，否则为 previous2
否则：
如果 res1 > res2，则：
previous2 的下一个节点 := previous1 的下一个节点
否则：
previous1 的下一个节点 := previous2 的下一个节点
previous1 := current1
previous2 := current2
如果 current1 不为 null，则：
current1 := current1 的下一个节点
如果 current2 不为 null，则：
current2 := current2 的下一个节点
显示 result 的内容。
示例
让我们来看下面的实现以获得更好的理解：
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
126 次浏览
