Pythonで2つのソート済みリストを1つにマージする方法

2つのソート済み（昇順に並べ替えられた）リストAとBがあるとします。これらをマージして、1つのソート済みリストCを作成することを目標とします。なお、2つのリストのサイズは同じである必要はありません。

例えば、A = [1, 2, 4, 7]、B = [1, 3, 4, 5, 6, 8] の場合、マージ後のリストCは [1, 1, 2, 3, 4, 4, 5, 6, 7, 8] となります。

アルゴリズムの考え方

この問題は再帰を使うことでシンプルに解くことができます。merge() 関数の動作は以下のようになります。

• 関数 merge() にリストAとBを渡す
• Aが空ならBを返し、Bが空ならAを返す（ベースケース）
• Aの先頭の値がBの先頭の値以下であれば、A.next = merge(A.next, B) としてAを返す
• そうでなければ、B.next = merge(A, B.next) としてBを返す

このように、各ステップで「小さい方のノードを選び、残りを再帰的にマージする」という処理を繰り返すことで、全体がソートされた1つのリストが構築されます。

Pythonでの実装例

実際のコードを見て、動作をより深く理解しましょう。ここでは連結リスト（Linked List）として実装しています。

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 mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2
        if not l2:
            return l1
        if l1.val <= l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

head1 = make_list([1, 2, 4, 7])
head2 = make_list([1, 3, 4, 5, 6, 8])
ob1 = Solution()
head3 = ob1.mergeTwoLists(head1, head2)
print_list(head3)

入力

head1 = make_list([1, 2, 4, 7])
head2 = make_list([1, 3, 4, 5, 6, 8])

出力

[1, 1, 2, 3, 4, 4, 5, 6, 7, 8]

計算量について

この再帰的なアプローチの計算量は以下の通りです。

• 時間計算量： O(m + n) — 2つのリストの各ノードをそれぞれ1回ずつ処理するため
• 空間計算量： O(m + n) — 再帰呼び出しによるスタック領域が必要となるため

なお、再帰ではなく反復処理（ループ）とダミーノードを使えば、空間計算量をO(1)に抑えることも可能です。ただし、再帰版はロジックが直感的で理解しやすいというメリットがあります。