Pythonで2つの連結リストの要素をインターリーブして1つにまとめる方法

2つの連結リスト(リンクリスト)l1とl2が与えられたとき、l1から始めて両方のリストの要素を交互に組み合わせた(インターリーブした)1つの連結リストを返すことを考えます。どちらかのリストにノードが余った場合は、その残りのノードを結果のリストの末尾にそのまま追加します。

例えば、入力が l1 = [5,4,6,3,4,7]、l2 = [8,6,9] の場合、出力は [5,8,4,6,6,9,3,4,7] となります。

アルゴリズムの手順

この問題を解くには、以下の手順に従います。

• ans := l1 と初期化する

• l2 が null でない限り、以下を繰り返す

  • ans が null でない場合

    • ans.next が null でない場合

      • newnode := l2 と同じ値を持つ新しいノードを作成する

      • newnode.next := ans.next

      • ans.next := newnode

      • ans := newnode.next

      • l2 := l2.next

    • それ以外の場合

      • ans.next := l2

      • ループを抜ける

  • それ以外の場合

    • l2 を返す

• l1 を返す

実装例(Python)

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

Source Code (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):
        ans = l1
        while l2:
            if ans:
                if ans.next != None:
                    newnode = ListNode(l2.val, None)
                    newnode.next = ans.next
                    ans.next = newnode
                    ans = newnode.next
                    l2 = l2.next
                else:
                    ans.next = l2
                    break
            else:
                return l2
                return l1

ob = Solution()
l1 = make_list([5,4,6,3,4,7])
l2 = make_list([8,6,9])
res = ob.solve(l1,l2)
print_list(res)

入力

[5,4,6,3,4,7],[8,6,9]

出力

[5, 8, 4, 6, 6, 9, 3, 4, 7]

アルゴリズムのポイント

このアルゴリズムでは、ポインタ ans を l1 上で進めながら、l2 の各ノードと同じ値を持つ新しいノードを ans と ans.next の間に挿入していきます。リンクの付け替えを繰り返すことで、2つのリストの要素が交互に並んだ状態を作れます。l1 側が先に末尾に達した場合は、l2 の残りのノードをそのまま連結して処理を終了します。計算量は O(n + m)(n、m はそれぞれのリストの長さ)となり、効率的に動作します。