2 本ずつまとめて k 本の並んだ連結リストを 1 本にする

連結リスト問題 170

小さい順に並んだ k 本の連結リストを、小さい順のまま 1 本につなぎ直して返します。2 本をまとめる手順を、組み合わせを半分ずつに減らしながら繰り返し、O(N log k) に収める練習です。

海外で定番の問題リスト 4 本には入っていません

問題

小さい順に並んだ連結リストの先頭を k 本集めた並び lists を受け取ります。k 本の節を全部使い、小さい順に並んだ 1 本のリストにつなぎ直して、その先頭の節を返す関数を書いてください。

各節は val (値) と next (次の節) を持ちます。最後の節の next は、Python では None、JavaScript では null、Go では nil です。Go の節は ListNode で、Val、Next と大文字で始まります。Go の lists は []*ListNode です
どのリストも小さい順に並んでいます。同じ値が何度出てもかまいません
lists は空のこともあり、中に空のリストが混じることもあります。節が 1 つも無ければ空のまま返します
k は 0 以上 100 以下、それぞれの節の数は 0 以上 50 以下、値はどれも -1000 以上 1000 以下です

例では、リストを先頭から読んだ値の並びで書きます。lists は、その並びを k 本並べた物です。

入力と出力の例

例 1

3 本の先頭は 3、1、4 です。8 は 2 本にあり、両方とも残ります。

lists = [[3, 8, 15], [1, 9], [4, 8, 20]]

[1, 3, 4, 8, 8, 9, 15, 20]

例 2

空のリストは何も足しません。節を持つのは 2 本目だけです。

lists = [[], [6], []]

[6]

例 3

4 本のうち 2 本が 1 つだけの節です。負の数も同じ比べ方で並びます。

lists = [[-5, 0], [-5], [2, 2, 7], [-1]]

[-5, -5, -1, 0, 2, 2, 7]

面接での聞かれ方

2 本をまとめる問題 (merge-sorted-lists) の続きとして、そのまま聞かれることが多い問題です。

「並んだ連結リストが k 本あります。1 本の並んだリストにまとめてください」
「ログを出すサーバーが k 台あり、どれも時刻の順に並んだ記録を持っています。全部を時刻の順に 1 本にしてください」と、場面を付けて聞かれることもあります
書き終えたあとに「優先度付きの待ち行列 (ヒープ) でも書けますか？」「k が 1 万、節の合計が 1 億ならどちらを選びますか？」と、もう 1 つの書き方と比べさせられます

シニアの問題なので、1 本ずつ順に足していく書き方が O(N k) になる理由を言え、O(N log k) に下げる手を自分から出せるかが見られます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

まずは素直に、1 本目に 2 本目をまとめ、その結果に 3 本目をまとめ、と順に足していく書き方を考えます。動きますが、まとめた結果はどんどん長くなり、それを毎回なめ直します。節の合計を N とすると、だいたい O(N k) かかります。

段 2

足す順を変えます。1 本目と 2 本目、3 本目と 4 本目、と隣どうしを 2 本ずつまとめると、1 回の組み合わせで本数が半分になります。どの節も 1 回の組み合わせで 1 度しか動かないので、1 回あたり O(N) です。

段 3

本数が半分ずつ減るので、1 本になるまでの回数は log k 回です。全体で O(N log k) になります。本数が奇数のときは、相手のいない最後の 1 本を空のリストとまとめれば、そのまま次の回へ持ち越せます。

段 4

2 本をまとめる所は、merge-sorted-lists と同じ書き方を使います。値を持たない目印の節 (ダミー) を先頭に置き、2 本の先頭を比べて小さい方をつなぎ、片方が尽きたら残りを丸ごとつなぎます。lists が空なら、まとめる物が無いので空を返します。

解答

Python

def merge_two(a, b):
    dummy = ListNode(0)
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a if a else b
    return dummy.next


def merge_k_lists(lists):
    if not lists:
        return None
    while len(lists) > 1:
        n = len(lists)
        merged = []
        for i in range(0, n, 2):
            a = lists[i]
            b = None
            if i + 1 < n:
                b = lists[i + 1]
            merged.append(
                merge_two(a, b)
            )
        lists = merged
    return lists[0]

JavaScript

function mergeTwo(a, b) {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a !== null
    && b !== null) {
    if (a.val <= b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}

function mergeKLists(lists) {
  if (lists.length === 0) {
    return null;
  }
  while (lists.length > 1) {
    const n = lists.length;
    const merged = [];
    for (let i = 0; i < n;) {
      const b = i + 1 < n
        ? lists[i + 1]
        : null;
      merged.push(
        mergeTwo(lists[i], b),
      );
      i += 2;
    }
    lists = merged;
  }
  return lists[0];
}

Go

func mergeTwo(
	a, b *ListNode,
) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for a != nil && b != nil {
		if a.Val <= b.Val {
			tail.Next = a
			a = a.Next
		} else {
			tail.Next = b
			b = b.Next
		}
		tail = tail.Next
	}
	if a != nil {
		tail.Next = a
	} else {
		tail.Next = b
	}
	return dummy.Next
}

func mergeKLists(
	lists []*ListNode,
) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	for len(lists) > 1 {
		n := len(lists)
		merged := []*ListNode{}
		for i := 0; i < n; i += 2 {
			var b *ListNode
			if i+1 < n {
				b = lists[i+1]
			}
			merged = append(merged,
				mergeTwo(lists[i], b))
		}
		lists = merged
	}
	return lists[0]
}

merged は 1 回の組み合わせでできたリストの並びです。本数が奇数のとき、最後の 1 本は空 (b が空) とまとめられ、そのまま次の回へ進みます。

計算量

時間は O(N log k) です。N は全部の節の数、k はリストの本数です。1 回の組み合わせでどの節も 1 度ずつ動いて O(N)、本数が半分ずつ減るので組み合わせは log k 回です
使う記憶は O(k) です。節はつなぎ直すだけで新しく作らず、1 回ごとにまとめたリストの先頭を入れる並び merged だけを持ちます。ヒープで書いても、k 本の先頭を入れておくので同じ O(k) です

よくある間違い

1 本ずつ順に足していく。答えは合いますが、まとめた長いリストを毎回なめ直すので O(N k) です。k が大きいと間に合わず、面接では「もっと速く」と必ず言われます
全部の値を並びに集めて並べ替え、節を作り直す。 O(N log N) で動きますが、もとから並んでいるという手がかりを使っていません。節を作り直すので記憶も O(N) 要ります
本数が奇数のときに最後の 1 本を落とす。 i + 1 が範囲の外になる所で止めると、例 1 の 3 本目 (4、8、20) が消えます。相手が無いときは空とまとめて残します
lists が空のときに lists[0] を読む。 0 本なら、まとめる前に空を返します。中に空のリストがあるだけなら、2 本をまとめる所がそのまま扱えます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # 連結リストの節は val、next を持ちます。最後の next は None です
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
# build_list は並びから連結リストを組みます
print(list_values(merge_k_lists([build_list([3, 8, 15]), build_list([1, 9]), build_list([4, 8, 20])])))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します