JavaでK個のソート済み連結リストを効率的にマージする方法

本記事では、それぞれ異なる長さを持ち、昇順にソートされたK個の連結リスト（Linked List）を、1つのソート済み結果リストへマージする方法を解説します。マージ後のリストは昇順に並べ替えられ、その結果がユーザーに出力されます。この問題は、JavaのPriorityQueue（優先度付きキュー）を使うことで、効率よく美しく実装できます。

具体例で理解しよう

入力 −

int k = 3;
list[0] = new Node(11);
list[0].next = new Node(15);
list[0].next.next = new Node(17);
list[1] = new Node(2);
list[1].next = new Node(3);
list[1].next.next = new Node(26);
list[1].next.next.next = new Node(39);
list[2] = new Node(4);
list[2].next = new Node(8);
list[2].next.next = new Node(10);

出力 − マージ後のリストは以下の通りです。

2>> 3>> 4>> 8>> 10>> 11>> 15>> 17>> 26>> 39>> null

解説 − 昇順にソートされた3つの連結リストが与えられています。マージ処理では、JavaのComparatorを使って各リストの先頭ノード同士を比較し、最も小さい値を持つノードから順に結果リストへ連結していきます。

入力 −

int k = 2;
list[0] = new Node(1);
list[0].next = new Node(4);
list[0].next.next = new Node(5);
list[1] = new Node(2);
list[1].next = new Node(3);
list[1].next.next = new Node(6);
list[1].next.next.next = new Node(8);

出力 − マージ後のリストは以下の通りです。

1>> 2>> 3>> 4>> 5>> 6>> 8>> null

解説 − この場合も同様に、2つのソート済みリストの先頭要素を比較しながら、小さい方のノードを結果リストの末尾へ順次追加していくことで、全体がソートされた1つのリストが完成します。

プログラムで使用するアプローチ

• マージ対象となるリストの個数（K）を入力として受け取ります。
• 連結リストのノードを生成するためのNodeクラスを定義します。各ノードはデータ（data）と次ノードへの参照（next）を持ちます。
• 各連結リストをソート済みの状態で初期化し、先頭ノードの配列とリスト数kを引数としてmergeLists関数に渡します。
• 関数内では、ノードの値を基準に並べるPriorityQueueを作成し、すべてのリストの先頭ノードをキューに登録します。
• キューが空になるまでループを回し、最小値のノードを取り出しては結果リストに連結します。最初に取り出したノードが結果リストの先頭（head）となります。
• 取り出したノードに次のノード（min.next）が存在する場合は、それをキューに再登録します。これにより、常に各リストの未処理の中で最小の候補だけがキューに残ります。
• すべてのノードを処理し終えたら、結果リストの先頭を呼び出し元に返します。

この手法の計算量は、全ノード数をN、リスト数をKとすると、時間計算量はO(N log K)、空間計算量はO(K)となり、単純な全比較方式（O(N×K)）よりも大幅に高速です。

サンプルコード

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Node {
    int data;
    Node next;
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class testClass {
    public static Node mergeLists(Node[] list, int k) {
        PriorityQueue<Node> priorityQueue;
        priorityQueue = new PriorityQueue<Node>(Comparator.comparingInt(a -> ((Node) a).data));
        priorityQueue.addAll(Arrays.asList(list).subList(0, k));
        Node head = null, last = null;
        while (!priorityQueue.isEmpty()) {
            Node min = priorityQueue.poll();
            if (head == null) {
                head = last = min;
            } else {
                last.next = min;
                last = min;
            }
            if (min.next != null) {
                priorityQueue.add(min.next);
            }
        }
        return head;
    }

    public static void main(String[] s) {
        int k = 3;
        Node[] list = new Node[k];
        list[0] = new Node(11);
        list[0].next = new Node(15);
        list[0].next.next = new Node(17);
        list[1] = new Node(2);
        list[1].next = new Node(3);
        list[1].next.next = new Node(26);
        list[1].next.next.next = new Node(39);
        list[2] = new Node(4);
        list[2].next = new Node(8);
        list[2].next.next = new Node(10);
        System.out.println("The merged list is-->");
        Node head = mergeLists(list, k);
        while (head != null) {
            System.out.print(head.data + ">> ");
            head = head.next;
        }
        System.out.print("null");
    }
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

The merged list is-->
2>> 3>> 4>> 8>> 10>> 11>> 15>> 17>> 26>> 39>> null

まとめ

K個のソート済み連結リストのマージには、PriorityQueueを活用するのが最も効率的です。各リストの先頭ノードだけをキューに保持することでメモリ使用量をO(K)に抑えつつ、O(N log K)の時間計算量で全体をソートされた1つのリストに統合できます。アルゴリズムの学習だけでなく、実務でのデータ統合処理にも応用できる重要なテクニックなので、ぜひマスターしておきましょう。