Pythonで連結リストをマージするプログラムの実装手順を解説

長さ m の連結リスト L1 と、長さ n の連結リスト L2 があるとします。さらに、2つの位置 a と b も与えられています。この問題では、L1 の a 番目のノードから b 番目のノードまでを削除し、その部分に L2 を挿入してマージします。

例えば、入力が L1 = [1,5,6,7,1,6,3,9,12]、L2 = [5,7,1,6]、a = 3、b = 6 の場合、出力は [1, 5, 6, 5, 7, 1, 6, 9, 12] になります。これは、L1 のインデックス 3〜6 に相当する「7, 1, 6, 3」が取り除かれ、代わりに L2 の「5, 7, 1, 6」が挿入されるためです。

アルゴリズムの流れ

この問題は、次の手順で解くことができます。

1. L2 の末尾を求める：head2 := L2、temp := L2 とし、temp に次のノードが存在する限り temp := next of temp と進めます。ループ終了時の temp が tail2（L2 の末尾ノード）になります。
2. 変数を初期化する：count := 0、temp := L1、end1 := null、start3 := null とします。
3. L1 を走査して接続点を記録する：temp が null でない間、以下を繰り返します。
   • count が a-1 と等しいとき、end1 := temp（削除範囲の直前のノード）
   • count が b+1 と等しいとき、start3 := temp（削除範囲の直後のノード）としてループを抜ける
   • temp := next of temp、count := count + 1 として次へ進む
4. リンクをつなぎ替える：end1 の next を head2 に、tail2 の next を start3 につなぎ直し、L1 を返します。

実装例

理解を深めるために、以下の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(']')

def solve(L1, L2, a, b):
    head2 = temp = L2
    while temp.next:
        temp = temp.next
    tail2 = temp

    count = 0
    temp = L1
    end1, start3 = None, None
    while temp:
        if count == a-1:
            end1 = temp
        if count == b+1:
            start3 = temp
            break
        temp = temp.next
        count += 1

    end1.next = head2
    tail2.next = start3
    return L1

L1 = [1,5,6,7,1,6,3,9,12]
L2 = [5,7,1,6]
a = 3
b = 6
print_list(solve(make_list(L1), make_list(L2), a, b))

入力

[1,5,6,7,1,6,3,9,12], [5,7,1,6], 3, 6

出力

[1, 5, 6, 5, 7, 1, 6, 9, 12]

計算量のポイント

このアルゴリズムは、L1 と L2 をそれぞれ一度ずつ走査するだけなので、時間計算量は O(m + n) です。また、新しいノードを生成せず既存ノードのポインタをつなぎ替えるだけで処理が完結するため、追加のメモリ使用量は O(1) で抑えられます。連結リストのマージ処理において非常に効率的なアプローチといえるでしょう。