Pythonでいくつかの共通ノードを持つ2つのソートされたリンクリストから最大合計リンクリストを作成します

ソートされたリンクリストが2つあるとすると、開始ノードから終了ノードまでの最大の合計パスで構成されるリンクリストを作成する必要があります。最終的なリストは、両方の入力リストのノードで構成されている場合があります。

結果リストを作成するときに、交点（リスト内の同じ値を持つ2つのノード）についてのみ、他の入力リストに切り替えることができます。一定量の余分なスペースを使用して解決する必要があります。

したがって、入力が[6,8,35,95,115,125]、[5,8,17,37,95,105,125,135]の場合、出力は[6,8,17,37,95,115,125,135]

これを解決するには、次の手順に従います-

• 結果：=なし

• previous1：=a、current1：=a

• previous2：=b、current2：=b

• current1はNoneと同じではないか、current2はNoneと同じではありませんが、実行してください

  • res1：=0、res2：=0

  • current1とcurrent2はnullではなく、current1のデータはcurrent2のデータと同じではありませんが、実行してください

    • current1のデータ

      • 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と同じ場合、

    • 結果：=previous1 when（res1> res2）それ以外の場合previous2

  • それ以外の場合

    • res1> res2の場合、

      • previous2の次：=previous1の次

    • それ以外の場合

      • previous1の次：=previous2の次

  • previous1：=current1

  • previous2：=current2

  • current1がnullでない場合、

    • current1：=current1の次

  • current2がnullでない場合、

    • current2：=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