Pythonで共通ノードを持つ2つのソート済み連結リストから最大合計パスのリストを作成する方法

ソート済みの連結リストが2つ与えられたとき、開始ノードから終了ノードまでの合計値が最大となるパスで構成される連結リストを作成することを考えます。最終的なリストには、両方の入力リストのノードが含まれる可能性があります。

結果のリストを作成する際、あるリストから別のリストへ切り替えられるのは、交点(両方のリストに同じ値を持つノード)の位置のみです。また、この問題は定数の追加メモリ(定数空間)で解く必要があります。

例えば、入力が [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 または current2 のどちらかが None でない限り、以下を繰り返す
  • res1 := 0、res2 := 0 と初期化する
  • current1 と current2 がどちらも NULL ではなく、かつ current1 のデータと current2 のデータが異なる間、次を繰り返す
    • current1.data < current2.data の場合:
      • res1 := res1 + current1.data
      • current1 := current1.next
    • それ以外の場合:
      • res2 := res2 + current2.data
      • current2 := current2.next
  • current1 が NULL の場合、current2 が NULL になるまで残りのノードの値を res2 に加算していく
  • current2 が NULL の場合、current1 が NULL になるまで残りのノードの値を res1 に加算していく
  • previous1 == a かつ previous2 == b(最初の交点より前)の場合:
    • result := (res1 > res2) ならば previous1、そうでなければ previous2
  • それ以外の場合:
    • res1 > res2 ならば、previous2.next := previous1.next とする
    • そうでなければ、previous1.next := previous2.next とする
  • previous1 := current1、previous2 := current2 と更新する
  • current1 が NULL でなければ、current1 := current1.next とする
  • current2 が NULL でなければ、current2 := current2.next とする
• 最後に result の内容を表示する

実装例

理解を深めるために、以下のPythonでの実装を見てみましょう。

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

処理のポイント

このアルゴリズムでは、2つのリストを同時に走査し、共通ノード(同じ値を持つノード)に到達するまでの各区間ごとに合計値(res1 と res2)を比較します。そして、合計値が大きい側の経路を採用することで、ポインタの接続先を付け替えていきます。この処理により、追加のリストを作成せずに既存のノードをつなぎ替えるだけで結果が得られるため、時間計算量 O(n + m)、追加空間計算量 O(1) で問題を解くことができます。