代表的な面接トピック

コーディング面接：k 個のソート済み連結リストをどのようにマージしますか？

コーディング難しい
Offer.cc 編集チーム公開日 更新日

質問

値が広義単調増加（昇順）にソートされた k 個の単方向連結リストが与えられたとき、それらを 1 つのソート済み連結リストにマージしてください。既存のノードを再利用し、空のリストや重複値を適切に処理し、時間計算量 O(N log k) および補助空間計算量 O(k) を目指してください。また、正当性、タイ（同値）の処理、代替手法、エッジケースについても説明してください。

問題の要件と適用されるコンテキスト

k 個の単方向連結リストの先頭ノードを格納した配列 lists が与えられたとき、すべてのノードを値が広義単調増加となる 1 つのリストにマージしてください。入力リストのいずれかが空である場合や、値が負数・重複値である場合もあり、すべての入力ノードの総数は N です。

各入力リストは非巡回であり、すでにソートされており、他の入力リストとノードを共有していないと仮定します。実装では既存のノードを繋ぎ直すことができ、すべての値に対して新しいノードを再割り当てしてはなりません。異なる入力リスト間での等しい値の順序についての規定はありません。配列が空であるか、すべての先頭ノードが None の場合は None を返してください。目標とする計算量は O(N log k) 時間および O(k) 補助空間です。

text
Input:
  1 -> 4 -> 5
  1 -> 3 -> 4
  2 -> 6

Output:
  1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

これは連結リストの問題であるため、ポインタの所有権はコントラクトの一部です。呼び出し元がすべての入力リストを変更しないことを要求する場合、アルゴリズムの選択自体は同じままで構いませんが、出力用に N 個の新しいノードを割り当てる必要があり、その出力空間は O(N) になります。

面接官が評価するポイント

最初の評価基準は、候補者がソート済みの構造を活用しているかどうかです。すべての値を平坦化してソートする方法も機能しますが、O(N log N) の時間と O(N) の追加ストレージを消費します。出力ノードごとにすべての現在の先頭ノードをスキャンする方法はソート済みの性質を利用しますが、O(Nk) のコストがかかります。優れた回答では、どの小さな集合に次の全体最小値が含まれ得るかを問いかけます。

2 つ目の基準は、フロンティア不変条件（frontier invariant）の理解です。まだ消費し尽くされていない各リストについて、次の出力ノードになり得るのはそのリストの未マージの先頭ノードのみです。そのリストはソートされているため、それ以降のすべてのノードはその先頭ノード以上の値になります。したがって、未完了のリストごとに 1 つのフロンティアノードを保持する最小ヒープを使用すると、最大 k 個の候補に対する線形スキャンを、最大サイズ k のヒープに対する最小値の取り出しと挿入に削減できます。

3 つ目の基準は、証明と計算量の説明です。選択されたノードがなぜ全体として最小であるのか、その後続ノードのみをプッシュすることでなぜ不変条件が回復するのか、なぜすべてのノードが厳密に 1 回だけ出力されるのか、そしてヒープサイズがなぜ非空リストの数を超えないのかを説明する必要があります。このような論証なしに「優先度付きキューを使用する」とだけ述べるのでは、中核となる推論が欠落してしまいます。

4 つ目の基準は、実装の厳密さです。Python では、数値の優先度が等しいヒープエントリが ListNode オブジェクト同士の比較にフォールスルーしてはなりません。一意のシーケンス番号を使用することでタイブレーカー（順位決定）を提供します。ノードを再利用する場合、ノードを切り離して追加する前に元の後続ノードを保存するため、構築されたプレフィックスには明確な所有権が 1 つあり、未マージのリストへの一時的なポインタを保持し続けることがありません。

最後の基準は、2 つの最適アプローチからの選択です。最小ヒープとバランスの取れたペアワイズマージ（分割統治）はどちらも O(N log k) 時間を達成します。ヒープはフロンティアを明示化し、イテレータやストリームへと自然に拡張できます。分割統治法は通常の 2 リストマージを使用し、先頭ノードの配列以外の定数ポインタ作業空間で動作できます。入力コントラクトによって、どちらの説明がより簡潔かが決まります。

回答前に確認すべき明確化のための質問

  • 入力ノードを変更して再利用してもよいですか？ はいの場合は、ポインタを繋ぎ直し、O(k) のヒープストレージのみを使用します。いいえの場合は、出力を割り当て、その O(N) 空間をアルゴリズムの補助状態とは区別して報告します。
  • すべての入力はソート済みかつ非巡回ですか？ 提示されたアルゴリズムはこれら両方を前提としています。ソート済みかどうかの検証には O(N) のコストがかかります。サイクルの検出も作業内容が変わるため、基本解に暗黙的に追加すべきではありません。
  • k は何をカウントしていますか？ 非空リストの数を m とします。ヒープが保持するのは最大で m 個であるため、より正確な計算量の上限は m >= 2 の場合に O(N log m) となり、非空リストが 0 個または 1 個の場合は線形時間の処理となります。
  • 等しい値はリスト間の順序を保持（安定性を維持）する必要がありますか？ 基本的な問題では値がソートされていることのみが求められます。安定なコントラクトを保証するには、ヒープキーにエンコードされた明確な元の順序が必要です。
  • 言語の組み込み優先度付きキューを使用してもよいですか？ 面接官がヒープの実装自体を個別にテストしているのでない限り、通常は可能です。二分ヒープをゼロから作成して面接時間を消費する前に確認してください。
  • これらは完全に実体化された連結リストですか、それとも遅延イテレータですか？ ヒープは両方を処理できますが、イテレータ版では現在の値が取り出されるまでソースを進めないようにする必要があります。
  • 入力の先頭ノード配列はどう処理すべきですか？ 以下のコードでは配列のエントリ自体は変更せず、そのノード群を繋ぎ直します。呼び出し元が両方を観察する場合は、その所有権の移転をドキュメントに明記してください。

30秒で伝える回答フレームワーク

「ソート済みリストの未マージの先頭ノードのみが次の全体最小値になり得るため、これらのフロンティアノードを最小ヒープで管理します。最小のノードをポップして結果に追加し、事前に保存したその後続ノードのみをプッシュします。不変条件は、ヒープが消費し尽くされていない各リストから厳密に 1 つのフロンティアを含んでいることであり、これによりポップされたノードの最小性が保証され、そのソースのフロンティアを補充することで不変条件が維持されます。N 個の各ノードは 1 回だけポップされ、最大 1 個の後続ノードがプッシュされ、ヒープサイズは最大 k であるため、時間計算量は O(N log k)、補助空間計算量は O(k) になります。既存ノードを再利用し、等しい値でノードオブジェクト同士が比較されないよう一意のタイブレーカーを追加し、空入力、重複、負数、不揃いな長さ、1 つのリストなどのケースをテストします。同じ時間上限を持つ主な代替案として、バランスの取れたペアワイズマージがあります。」

ステップバイステップの詳細解説

まずは単純な代替手法から確認し、重複する処理を特定します。

アプローチ時間計算量補助空間計算量重複または破棄される情報
値を平坦化、ソート、再構築O(N log N)O(N)すべての入力がすでにソートされている事実を破棄
ノードごとに最大 k 個の先頭をスキャンO(Nk)O(1)線形な最小値探索を N 回繰り返す
1 つのアキュムレータに逐次マージ最悪 O(Nk)O(1)初期のノードがその後の多数のマージで何度も走査される
バランスの取れたペアワイズマージO(N log k)O(1) ポインタ作業空間マージレベルごとにすべてのノードを 1 回処理する
フロンティアの最小ヒープO(N log k)O(k)次のソースを選択するためにヒープ操作を行う

逐次マージは過小評価されがちです。k 個のリストがほぼ同じ長さ L を持つ場合、作業量は 2L + 3L + ... + kL のように増加し、これは O(Lk²) です。N = Lk であるため、これは O(Nk) になります。ペアワイズマージはラウンドごとに対でリストを結合することで不均衡なアキュムレータを回避し、すべてのノードが関与するマージレベルを最大 ceil(log₂ k) レベルに抑えます。

ヒープ解法では、各取り出しの前に以下の不変条件を維持します。

text
For each non-exhausted input list:
  the heap contains exactly its first unmerged node.

For each exhausted input list:
  the heap contains no node from that list.

The result contains every previously removed node exactly once,
in non-decreasing order.

初期化時に各非空リストの先頭を挿入するため、不変条件は成り立ちます。ある反復の開始時にこれが成り立っていると仮定します。未マージのノードは、ヒープ内のフロンティアであるか、そのリストのフロンティアより後ろに現れます。各入力はソートされているため、それ以降のノードがそのフロンティアより小さくなることはありません。したがって、ヒープの最小エントリはどの未マージノードよりも大きくならず、安全に追加できます。

ノードを取り出した後、そのソースリストのみが代表を失います。そのノードの元の後続ノードを保存し、ノードを切り離して追加し、後続ノードが存在する場合はそれをヒープに挿入します。他のすべてのソースフロンティアは有効なままであるため、不変条件が回復します。各反復で 1 つのノードが出力され、厳密に N 回の反復の後にすべてのリストが消費し尽くされ、ヒープは空になります。これにより、ソート性、完全性、および終了性が証明されます。

以下の Python 実装では、2 番目のタプルフィールドとして単調増加するシーケンス番号を使用します。この番号は一意であるため、値が等しい場合でもタプル比較が順序付け不能なノードオブジェクトに到達することはありません。

python
from __future__ import annotations

from dataclasses import dataclass
from heapq import heappop, heappush
from itertools import count


@dataclass
class ListNode:
    val: int
    next: ListNode | None = None


def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
    heap: list[tuple[int, int, ListNode]] = []
    sequence = count()

    for head in lists:
        if head is not None:
            heappush(heap, (head.val, next(sequence), head))

    dummy = ListNode(0)
    tail = dummy

    while heap:
        _, _, node = heappop(heap)
        next_node = node.next
        node.next = None
        tail.next = node
        tail = node

        if next_node is not None:
            heappush(heap, (next_node.val, next(sequence), next_node))

    return dummy.next

初期挿入は m 回あり、ここで m <= k は非空リストの数です。すべてのノードは 1 回取り出され、最後の末尾ノードを除くすべてのノードが最大 1 回の挿入を発生させます。ヒープのエントリ数が最大 m 個の間、ヒープ操作のコストは O(log m) です。m >= 2 の場合、合計時間は O(N log m)（一般的には O(N log k) と表記）となり、m <= 1 の場合、走査は O(N) となります。ヒープ、シーケンスカウンタ、ダミーノード、およびポインタは O(m) の補助空間を使用します。返されるノードは元のノードであるため、これらは新たなアルゴリズム用ストレージではなく出力です。

後続ノードはあらかじめ保存されているため、後続ノードを見つけるために node.next を切り離す必要はありません。しかし、これにより所有権が明示的になります。マージ済みのプレフィックスが、まだヒープで選ばれていないソースリストを一時的に指し示すことがなくなります。次の追加処理で末尾ノードの後続ポインタが設定されます。非巡回かつ素集合の入力コントラクトのもとでは、アルゴリズムが値を変更したり、同じノードを 2 回挿入したりすることはありません。

正常系の配列だけでなく、構造に着目したテストを実行します。

python
def build(values: list[int]) -> ListNode | None:
    dummy = ListNode(0)
    tail = dummy
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next


def values(head: ListNode | None) -> list[int]:
    result: list[int] = []
    while head is not None:
        result.append(head.val)
        head = head.next
    return result


cases = [
    ([], []),
    ([[]], []),
    ([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]),
    ([[], [-3, -1, 2], [], [-3, 7]], [-3, -3, -1, 2, 7]),
    ([[5]], [5]),
]

for raw_lists, expected in cases:
    actual = values(merge_k_lists([build(items) for items in raw_lists]))
    assert actual == expected, (raw_lists, expected, actual)

本番品質の検証を行う場合は、すべての入力ノードの同一性（identity）も記録し、訪問済みセットを用いて出力を走査し、「サイクルがないこと」「厳密に N 個の一意なノード同一性が存在すること」「値が広義単調増加であること」の 3 つの性質を証明します。これにより、値のみのアサーションでは見落とされる可能性のある二重挿入、ノードの欠落、およびポインタサイクルを検出できます。

面接官がポインタ操作を求めている場合、優先度付きキューが使用できない場合、またはヒープストレージの最小化が重要な場合は、バランスの取れたペアワイズマージを選択してください。ソースがイテレータとして公開されている場合、アクティブなソースの数が変化する場合、または「次の全体候補」を選択するメカニズムを明示化して分かりやすさを向上させたい場合は、ヒープを選択してください。どちらも基本コントラクトの下で有効な最適解です。その選択理由を述べるようにしてください。

質の高い模範解答

「入力ノードを再利用し、すべてのリストがソート済み、非巡回、かつ互いに素であると仮定します。ノードの総数を N、非空リストの数を m とします。次の出力になり得るのは m 個の現在の先頭ノードのいずれかのみです。それ以降のノードは、その先頭ノード以上の値になるためです。したがって、非空リストごとに 1 つの先頭ノードを最小ヒープに格納します。

私の不変条件は、ヒープに消費し尽くされていない各リストから厳密に未マージの先頭ノードが 1 つ含まれ、出力にはポップされたすべてのノードがソート順で 1 回ずつ含まれるというものです。最小値を取り出し、その後続ノードを保存して切り離し、ノードを追加して、保存した後続ノードをプッシュします。取り出されたノードは、他のすべての未マージノードがヒープ内の同等以上のフロンティアの後ろにあるため、全体として安全に最小です。後続ノードをプッシュすることで、1 リストあたり 1 フロンティアという不変条件が回復します。

Python では、エントリを (value, sequence, node) とします。一意のシーケンス値により、優先度が等しい場合にノードオブジェクト同士が比較されるのを防ぎます。問題文で要求されていないため、リスト間の安定した順序を保証するものではありません。各ノードは 1 回ポップされ、最大 1 回挿入され、ヒープエントリは最大 m 個です。これにより時間計算量は O(N log m)（通常は O(N log k) と表記）、補助空間計算量は O(m) となり、非空リストが 0 個または 1 個の場合は線形になります。

空の配列、すべて空のリスト、リストが 1 つ、長さが不揃い、負数、等しい値などのケースをテストします。また、解法がポインタを繋ぎ直すため、ノードの同一性とサイクルの非存在も検証します。主な代替案としてバランスの取れたペアワイズマージがあります。これも計算量は O(N log k) であり、2 リストのマージプリミティブのみを使用するため、面接でポインタコードが重視される場合や標準のヒープが使用できない場合はそちらを選択します。」

よくある間違い

  • すぐに平坦化してソートする → ソート済みの入力を無視し、O(N log N) に加えて出力ストレージを消費してしまう → ソート済みソースごとに 1 つのフロンティアを維持する。
  • ノードごとに対象となるすべての k 個の先頭をスキャンする → 最小値の選択が O(Nk) になる → サイズ k の最小ヒープまたはバランスの取れたペアワイズマージを使用する。
  • 1 つのリストを肥大化する結果に繰り返しマージする → 初期のノードがその後の多数のマージで繰り返し走査される → バランスの取れたラウンド形式でリストを結合する。
  • すべてのノードをヒープにプッシュする → ヒープサイズが N まで増大し、O(N log N) の計算量になる → 各ソースから現在のノードを 1 つだけプッシュする。
  • Python のヒープに (value, node) を格納する → 等しい値で順序付けできないノードオブジェクト同士を比較しようとしてしまう → 一意な数値のタイブレーカーを追加する。
  • 後続ノードを保存する前にソースを進める → ポインタの繋ぎ直しによって残りのリストを見失う可能性がある → 最初に後続ノードを保存してから、切り離して追加する。
  • ノードを再利用しているため空間計算量が O(1) であると主張する → ヒープは依然として最大 k 個のエントリを保持する → 出力の割り当てと補助状態を明確に区別する。
  • 出力の値のみを検証する → サイクル、ノードの重複、ノードの欠落が見落とされる可能性がある → ノードの同一性、総数、順序、およびサイクルの有無を確認する。
  • 明確化を行わずにソート検証やサイクル検出を追加する → より広範なコントラクトを解決することになり、コストが変化する → 前提条件を述べ、求められた場合にのみ検証を追加する。

フォローアップの質問と回答

なぜヒープの最小値が次の全体最小値になるのですか？

消費し尽くされていない各ソート済みリストから、その未マージの最初のノードが提供されています。その他のノードはこれらのフロンティアの背後にあり、それらより小さくなることはあり得ません。したがって、最も小さいフロンティアはどの未マージノードよりも大きくなることはありません。それを取り出すことは安全であり、その後続ノードを挿入することでそのソースのカバー範囲が復元されます。

等しい値について入力リスト順の安定性を保つ必要がある場合、何を変更しますか？

安定性を厳密に定義した上で、値に続いて入力リストのインデックスをヒープキーとして使用します。ソースごとに 1 つのノードしか存在しないため、ソースインデックスによってリスト間の同値が解決され、各リスト自体の順序は自然に保持されます。基本コードのシーケンスによるタイブレーカーは比較可能性を保証するものであり、そのような強い順序付けポリシーを保証するものではありません。

分割統治法がヒープより優れているのはどのような場合ですか？

2 つのリストのマージがすでに利用可能な場合、面接でポインタ操作が重視されている場合、または優先度付きキューが利用できない場合は、バランスの取れたペアワイズマージを使用します。各ラウンドは残りのすべてのノードを 1 回走査し、O(log k) ラウンド存在します。遅延ソースを扱う場合や、アクティブなソース数が動的に変化する場合は、ヒープの方が分かりやすくなります。

入力リストを変更してはならない場合はどうしますか？

同じ選択ロジックを維持しますが、取り出された値ごとに新しいノードを割り当てます。時間計算量は O(N log k) のままです。選択用の補助状態は O(k) のままで、必要な出力割り当ては O(N) になります。空間計算量の主張の中に出力メモリを紛れ込ませず、両方を明記してください。

10,000 個のリスト枠があるものの、5 個しか非空リストがない場合はどうなりますか？

初期化処理で k 個の枠を 1 回スキャンした後は、ヒープには最大 m = 5 個のエントリしか含まれません。正確な時間計算量は O(k + N log m)、補助空間計算量は O(m) です。単に O(N log k) と報告するだけでも上界としては安全ですが、空の先頭ノードをスキップするメリットが隠れてしまいます。

連結リストではなくソート済みイテレータをマージするにはどうしますか？

非空の各イテレータから 1 つずつ値を読み取り、ソースの識別情報とともにヒープに格納します。最小値を yield した後、そのソースのみを進めて次の値を挿入します。フロンティアの証明は変わらず、結果を遅延評価でき、メモリは全値の総数ではなくアクティブなソース数に比例したままになります。

後続ノードを持つノードを取り出した後、heapreplace を使用できますか？

個別の heappop を行った後には使用できません。古いルートはすでにヒープから離れているためです。実装としては、事前に先頭を確認（peek）し、ルートのソースを保存し、そのソースに後続ノードがある場合は 1 回の操作でルートを置き換えることも可能ですが、ソースが消費し尽くされた場合の分岐処理は残ります。より単純な「ポップしてプッシュする」コードの方が面接で正当性を証明しやすく、漸近的な計算量の上限も同じです。

具体例による確認を超えて、ポインタの正当性をテストするにはどうしますか？

マージ前にすべての入力ノードの同一性を記録します。重複する同一性を拒否しながら結果を走査し、厳密に N 個のノードをカウントし、すべての隣接する値をチェックし、ノードの同一性セットが一致していることを確認します。ソート済みリストをランダムに生成し、信頼できる「平坦化してソートする」オラクルと値を比較します。このオラクルはテストの検証用であり、本番の計算量要件を満たすものではありません。

公開情報ソース

Merge K Sorted Lists

Hello Interview

Merge k Sorted Lists

LeetCode

Frustrated

Reddit / r/leetcode

heapq — Heap Queue Algorithm

Python Software Foundation

MinPQ.java

Princeton University Algorithms, 4th Edition

COS 226 Assignment 2: Sorting, Merging, Heaping

Princeton University

関連する質問

コーディング面接：2ポインタ法で雨水トラップ問題（Trapping Rain Water）を解く方法質問と回答を開くコーディング面接：ダイクストラ法による最短経路アルゴリズムの実装質問と回答を開くコーディング面接：Union-Find の実装と連結成分の追跡方法質問と回答を開く

関連面接ツール

コーディング問題にはスクリーンショットを使用

問題をキャプチャし、制約条件、解法アプローチ、コード、エッジケース、計算量の順に進めます。

ツールを見る
無料で登録