从两个在Python中具有一些Common节点的排序链表中构造一个最大和链表

假设我们有两个排序的链表，我们必须制作一个链表，该链表包含从起点到终点的最大和路径。最终列表可能包含来自两个输入列表的节点。

在创建结果列表时，我们可能仅针对相交点（列表中具有相同值的两个节点）切换到其他输入列表。我们必须使用恒定量的额外空间来解决它。

因此，如果输入像[6,8,35,95,115,125]，[5,8,17,37,95,105,125,135]，则输出将为[6,8,17,37,95,115,125,135]

为了解决这个问题，我们将遵循以下步骤-

• 结果：=无

• 上一页1：= a，当前1：= a

• 上一页2：= b，当前2：= b

• 当current1不等于None或current2不等于None时，执行

• current2：= current2的下一个

• current1：= current1的下一个

• 如果res1> res2，则

• 除此以外，

• 下一个上一个2：=下一个上一个1

• next1的下一个：= previous2的下一个

• 结果（= res1> res2）时为previous1，否则为previous2

• 当current1不为null时，执行

• res1：= res1 + current1的数据

• current1：= current1的下一个

• 当current2不为null时，执行

• res2：= res2 + current2的数据

• current2：= current2的下一个

• 如果current1的数据<current2的数据，则

• 除此以外，

• res1：= res1 + current1的数据

• current1：= current1的下一个

• res2：= res2 + current2的数据

• current2：= current2的下一个

• res1：= 0，res2：= 0

• 当current1和current2不为null并且current1的数据与current2的数据不同时，执行

• 如果current1为null，则

• 如果current2为null，则

• 如果previous1与a相同，previous2与b相同，则

• 除此以外，

• 上一页1：=当前1

• previous2：=当前2

• 如果current1不为null，则

• 如果current2不为null，则

• 显示结果的内容。

示例

让我们看下面的实现以更好地理解-

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