Pythonで2つのソート済みリンクリストの和集合（結合）を求めるプログラム

2つのソート済み連結リスト L1 と L2 が与えられたとします。このとき、両方のリストの和集合（ユニオン）に相当する、新しいソート済み連結リストを作成して返す必要があります。

例えば、入力が以下のような場合を考えてみましょう。

• L1 = [10, 20, 30, 40, 50, 60, 70]
• L2 = [10, 30, 50, 80, 90]

この場合、出力は重複を除いた [10, 20, 30, 40, 50, 60, 70, 80, 90] となります。

解法のアプローチ

この問題は、再帰を使って両リストの先頭要素を比較しながら処理を進めることで解決できます。手順は以下の通りです。

1. 関数 solve() を定義します。引数として L1 と L2 を受け取ります。
2. L1 が空の場合は、L2 をそのまま返します。
3. L2 が空の場合は、L1 をそのまま返します。
4. L1 の値が L2 の値より小さい場合：
   • res := L1 とする
   • res の next には solve(L1 の次のノード, L2) の結果を代入する
5. L2 の値が L1 の値より小さい場合：
   • res := L2 とする
   • res の next には solve(L2 の次のノード, L1) の結果を代入する
6. 両者の値が等しい場合（重複の排除）：
   • res := L1 とする
   • res の next には solve(L1 の次のノード, L2 の次のノード) の結果を代入する
7. 最後に res を返します。

実装例

それでは、実際のコード実装を見てみましょう。

class ListNode:
   def __init__(self, data, next = None):
      self.val = data
      self.next = next

def make_list(elements):
   head = ListNode(elements[0])
   for element in elements[1:]:
      ptr = head
      while ptr.next:
         ptr = ptr.next
      ptr.next = ListNode(element)
   return head

def print_list(head):
   ptr = head
   print('[', end = "")
   while ptr:
      print(ptr.val, end = ", ")
      ptr = ptr.next
   print(']')

class Solution:
   def solve(self, L1, L2):
      if not L1:
         return L2
      if not L2:
         return L1
      if L1.val < L2.val:
         res = L1
         res.next = self.solve(L1.next, L2)
      elif L2.val < L1.val:
         res = L2
         res.next = self.solve(L2.next, L1)
      else:
         res = L1
         res.next = self.solve(L1.next, L2.next)
   return res

ob = Solution()
L1 = make_list([10,20,30,40,50,60,70])
L2 = make_list([10,30,50,80,90])
print_list(ob.solve(L1, L2))

入力

[10,20,30,40,50,60,70], [10,30,50,80,90]

出力

[10, 20, 30, 40, 50, 60, 70, 80, 90]

コードのポイント

このアルゴリズムの計算量は、O(m + n) です。ここで m と n はそれぞれ L1 と L2 の長さを表します。各再帰呼び出しで必ずどちらかのリストのポインタが進むため、全体で各ノードを一度だけ処理すればよいことになります。

また、値が等しいノードが見つかった場合は片方だけを採用し、両方のポインタを同時に進めることで重複を自動的に排除しています。これにより、マージソートのマージ処理に似た効率的な手法で和集合を構築できるのが特徴です。