Pythonで2つのソート済み連結リストの交差（共通要素）を求めるプログラム

問題の概要

2つのソート済み連結リスト（リンクリスト）L1 と L2 が与えられたとき、両方のリストに共通して含まれる要素だけからなる、新しいソート済み連結リストを作成することを考えます。これは、いわゆる「リストの交差」を求める問題です。

例えば、入力が L1 = [2, 4, 8]、L2 = [3, 4, 8, 10] の場合、両方のリストに存在する要素は 4 と 8 のみなので、出力は [4, 8] になります。

解き方のアプローチ

両方のリストがすでにソートされているため、各リストの先頭から2つのポインタを同時に進めていくことで、効率的に共通要素を抽出できます。具体的な手順は以下の通りです。

• 値 0 を持つダミーノードを作成し、head とします。
• cur に head を代入します。
• l1 と l2 のどちらも空でない間、以下の処理を繰り返します。
  • l1 の値が l2 の値より小さい場合：l1 を次のノードへ進めます。
  • l2 の値が l1 の値より小さい場合：l2 を次のノードへ進めます。
  • それ以外（両者の値が等しい場合）：cur の next として l1 と同じ値を持つ新しいノードを作成し、l1・l2・cur をそれぞれ次へ進めます。
• ループが終わったら、head.next を返します（ダミーノードを除いた結果のリスト）。

リストの長さをそれぞれ n、m とすると、計算量は O(n + m) となり、各ノードを一度ずつしか走査しないため非常に効率的です。また、ダミーノードを使用することで、結果リストの先頭の扱いがシンプルになり、コード全体も読みやすくなります。

実装例

それでは、上記の手順をPythonで実装したコードを見てみましょう。

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):
        head = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                l1 = l1.next
            elif l2.val < l1.val:
                l2 = l2.next
            else:
                cur.next = ListNode(l1.val)
                l1 = l1.next
                l2 = l2.next
                cur = cur.next
        return head.next

ob = Solution()
L1 = make_list([2, 4, 8])
L2 = make_list([3, 4, 8, 10])
print_list(ob.solve(L1, L2))

入力

[2, 4, 8], [3, 4, 8, 10]

出力

[4, 8]

出力の末尾に余分なカンマが表示されるのは、print_list 関数が各要素の後にカンマを出力する仕様になっているためです。リストの内容としては、正しく共通要素の [4, 8] が得られています。