ダミーの節で 2 本の並んだ連結リストを 1 本にまとめる｜コーディング面接問題

問題

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

各節は val (値) と next (次の節) を持ちます。最後の節の next は、Python では None、JavaScript では null、Go では nil です。Go の節は ListNode で、Val、Next と大文字で始まります
どちらのリストも小さい順に並んでいます。同じ値が続くこともあります
今ある節のつなぎ先を付け替えてまとめてください。比べるための目印の節 (ダミー) は 1 つ作ってかまいません
どちらか、または両方のリストが空のこともあります。両方が空なら空のまま返します
それぞれの節の数は 0 以上 50 以下、値はどれも -100 以上 100 以下です

例では、リストを先頭から読んだ値の並びで書きます。

入力と出力の例

例 1

同じ値の 5 は、両方とも残ります。

入力

head1 = [2, 5, 9]
head2 = [1, 5, 6, 12]

出力

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

例 2

片方が空なら、もう片方がそのまま答えです。

入力

head1 = []
head2 = [4, 7]

出力

[4, 7]

例 3

両方とも空です。

入力

head1 = []
head2 = []

出力

[]

面接での聞かれ方

連結リストの基本として、とてもよく出ます。

「並んだ 2 本の連結リストを、並んだ 1 本にまとめてください」
書き終えたあとに「k 本のリストならどうしますか？」と続きを聞かれることがあります。2 本ずつまとめる書き方と、優先度付きの待ち行列 (ヒープ) で k 本の先頭を比べる書き方があり、後者はシニアの問題です
「ダミーの節を使わずに書けますか？」「再帰でも書けますか？」と、書き方を変えて聞かれることもあります

ジュニアの問題なので、片方が先に尽きたときと、空のリストが来たときを、余分な場合分けなしに書けるかが見られます。

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

まず考える手順

段 1

まずは素直に、2 本の値を全部 1 つの並びに集め、並べ替えてから節を作り直す書き方を考えます。動きますが、並べ替えに O(n log n) かかり、もとから並んでいるという手がかりを使っていません。

段 2

2 本とも小さい順なので、まとめたリストの次に来るのは、必ずどちらかの先頭です。2 本の先頭を比べて小さい方を選び、つなぐ先の後ろへつなぎ、選んだ側を 1 つ進めます。これを繰り返せば、1 回なめるだけでまとまります。

段 3

最初の 1 つをつなぐときだけ、「まだ先頭が無い」という場合分けが要りそうです。そこで、値を持たない目印の節 dummy を作り、その後ろへつないでいきます。最後に dummy.next を返せば、先頭の場合分けも、両方が空の場合も 1 つの書き方で済みます。

段 4

どちらかが尽きたら、残りの側はもう小さい順に並んでいて、どれも今つないだ値以上です。1 つずつ移さず、残りの先頭を丸ごとつなげば終わりです。

解答

Python

def merge_sorted_lists(
    head1, head2
):
    dummy = ListNode(0)
    tail = dummy
    a, b = head1, head2
    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

JavaScript

function mergeSortedLists(
  head1, head2
) {
  const dummy = new ListNode(0);
  let tail = dummy;
  let a = head1;
  let b = head2;
  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;
}

Go

func mergeSortedLists(
	head1, head2 *ListNode,
) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	a, b := head1, head2
	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
}

tail は、まとめたリストの今の最後の節です。値が同じときに <= で head1 側を先に取るので、同じ値どうしの順も崩れません。

計算量

時間は O(n + m) です。n と m は 2 本の節の数で、どの節も 1 回だけつなぎます。残りを丸ごとつなぐ所は 1 回で済みます
使う記憶は O(1) です。ダミーの節 1 つと指だけで、ほかの節は今ある物をつなぎ直しています

よくある間違い

片方が尽きたあと、残りをつなぎ忘れる。繰り返しを抜けたところで終えると、例 1 の 9 と 12 のような残りが消えます。最後に残った側を丸ごとつなぎます
dummy を返す。 dummy は目印で値を持たないので、返すのは dummy.next です。dummy を返すと、先頭に 0 が 1 つ増えます
tail を進め忘れる。 つないだあとに tail = tail.next が無いと、毎回 dummy の後ろを上書きし、最後につないだ節から先しか残りません
ダミーを使わずに、先頭の場合分けで迷う。空のリストや片方だけ空の場合を別々に書き始めると、抜けが出やすくなります。ダミーを置けば、1 つの繰り返しで全部の場合が通ります

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

def merge_sorted_lists(head1, head2): # 連結リストの節は val、next を持ちます。最後の next は None です # ここに書きます pass # 「実行」を押すと、この行の結果が出ます # build_list は並びから連結リストを組みます print(list_values(merge_sorted_lists(build_list([2, 5, 9]), build_list([1, 5, 6, 12]))))

ダミーの節で 2 本の並んだ連結リストを 1 本にまとめる

問題