ソート済みリンクリストの merge
ソート済みリンクリストの merge
このレッスンで分かること
- 比較するのは 2 つのカーソルが指す要素だけ
- JavaScript も同じロジックです
- 2 つのソート済みリストを 1 つに合体させる操作は、
merge sortの核となる処理であり、技術面接でもよく出題されます
ソート済みリンクリストの merge とは
ソート済みの 2 つの連結リストを 1 つにマージし、merge sort の核となる手法を理解する。
2 つのソート済みリストを 1 つに合体させる操作は、merge sort の核となる処理であり、技術面接でもよく出題されます。リンクリストの場合は ポインタを付け替える だけでできるため、追加のメモリがほぼ不要なのが強みです。配列でやる場合は新しい配列を用意して詰め直すのが普通です。
本コースでは配列表現を使うため、arr1 = [1, 3, 5] と arr2 = [2, 4, 6] のような 2 つのソート済み配列を渡されたら、[1, 2, 3, 4, 5, 6] を返す関数を実装します。標準ライブラリの sort を使えば 1 行ですが、ここでは 2 ポインタ法 を学ぶのが目的です。
ソート済み 2 配列のマージは 2 ポインタ法 で
O(n + m)。両端のカーソルを進めながら小さい方を選ぶ。
2 ポインタ法のアイデア
i = 0、j = 0 の 2 つのインデックスを用意します。arr1[i] と arr2[j] を比較して、小さい方を結果に追加し、対応する方のインデックスを 1 進めます。どちらかが末尾に達したら、残りを丸ごとくっつけて完了です。
比較するのは 2 つのカーソルが指す要素だけ。バラバラに動かさず、片方ずつ進める。
ビジュアルで理解する
図のポイント (テキスト併記)
- 2 つの入力リストを比較しながら結果リストに 1 つずつ取り出していく、というイメージです
2 つの入力リストを比較しながら結果リストに 1 つずつ取り出していく、というイメージです。元の arr1 と arr2 を破壊する必要はありません。
Python での実装
Python
def mergeSortedLists(arr1, arr2):
result = []
i, j = 0, 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
while i < len(arr1):
result.append(arr1[i])
i += 1
while j < len(arr2):
result.append(arr2[j])
j += 1
return result3 つの while ループが特徴です。最初のループは「両方にデータが残っている間」、2 つ目と 3 つ目は「片方が尽きた後の残り処理」です。
JavaScript での実装
JavaScript
function mergeSortedLists(arr1, arr2) {
const result = [];
let i = 0, j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] <= arr2[j]) {
result.push(arr1[i]);
i++;
} else {
result.push(arr2[j]);
j++;
}
}
while (i < arr1.length) result.push(arr1[i++]);
while (j < arr2.length) result.push(arr2[j++]);
return result;
}JavaScript も同じロジックです。arr1.concat(arr2).sort((a, b) => a - b) でも結果は得られますが（比較関数なしの sort() は数値を文字列比較するため数値の場合は正しく動きません）、O((n+m) log(n+m)) になるため、O(n+m) の 2 ポインタ法の方が高速です。
よくある間違い
1 つ目は 片方が尽きた後の残り処理を忘れる ことです。最初の while を抜けた時点で、どちらかにまだ残りがあります。それを忘れて捨ててしまうと結果が短くなります。2 つ目は < と <= の混同 です。<= を使えば安定ソート (同じ値の元の順序が保たれる) になります。3 つ目は 空配列の扱い です。片方が空なら、もう片方をそのまま返せば OK です。while の条件で自然に対応できます。
やってみよう
[1, 3, 5]と[2, 4, 6]を渡したら[1, 2, 3, 4, 5, 6]が返るか確認する。[]と[1, 2, 3]を渡したら[1, 2, 3]が返るか確認する。- 本物のリンクリストで書いてみる。ダミーヘッド
dummyを用意してtail = dummyから始めて、tail.next = l1 or l2でポインタを付け替える形になる。
ダミーヘッドのテクニック
本物のリンクリストでマージを書くとき、ダミーヘッド を使うとコードがすっきりします。dummy = Node(0) のように空のノードを 1 つ用意し、それを起点に tail.next = ... で結果を組み立てていきます。最後に return dummy.next で本来の先頭を返します。これにより「先頭ノードを特別扱いする分岐」が消え、ループ内のロジックが統一されます。
Python
# 本物のリストでのマージ (参考)
def merge(l1, l2):
dummy = Node(0)
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 if l1 else l2
return dummy.nextこの ダミーヘッド のパターンは、連結リスト系のあらゆる問題で再利用できる便利テクニックです。覚えておくと一気にコードが書きやすくなります。
ダミーヘッドは 先頭の特別扱い を消すための定番テク。連結リスト系の問題で頻繁に登場する。
merge sort との関係
本レッスンの merge は単体で使うより、merge sort の核として登場することが多いです。merge sort は配列を半分に分割し、それぞれを再帰的にソートし、最後に本レッスンの merge で 1 つに統合する、というアルゴリズム。O(n log n) で動き、ソートアルゴリズムの王道です。merge sort は quick sort と並ぶ代表的なソートアルゴリズムで、O(n log n) かつ安定という特長があります。ソートの基本として押さえておきましょう。
merge sort は
分割+mergeの組合せ。mergeは本レッスンの 2 ポインタ法そのもの。
マージは 2 ポインタ法 が王道。
merge sortの半分はこのマージで、もう半分は再帰的な分割で構成される。
よくある質問
Q. リンクリストと配列はどう使い分けますか？
A. 配列はランダムアクセス O(1)、リンクリストは先頭への追加 O(1) が強みです。ほとんどの実用ケースで配列の方が速く、リンクリストはアルゴリズム問題の練習や特殊用途（OS のスケジューラ等）で使われる程度です。
Q. サイクル検出はどう実装しますか？
A. Floyd の循環検出（2 ポインタ法、tortoise and hare）が定番です。slow を 1 ステップ、fast を 2 ステップ進めると、ループがあれば必ず同じノードで出会います。空間 O(1) で動くのが優秀な点です。
Q. リンクリストを反転するコツは？
A. prev, curr, next の 3 ポインタを使い、curr.next = prev で 1 個ずつ繋ぎ替えます。再帰版でも書けますが、反復版の方がスタック消費が無く安全です。LeetCode の Reverse Linked List が定型問題なので解いておくと良いです。
次のレッスン
次は リンクリストの中央ノード取得 で、ソート済みの 2 つの連結リストを 1 つにマージし、merge sort の核となる手法を理解する を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- リンクリスト merge の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. リンクリスト merge とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 両方の配列は昇順ソート済みであると仮定して良い
- 2 ポインタ法で O(n + m) で実装すること
- 戻り値は昇順ソートされた新しい配列
入出力例
test-cases.txt
mergeSortedLists([1,3,5], [2,4,6]) → [1,2,3,4,5,6]
mergeSortedLists([1,2,3], [4,5,6]) → [1,2,3,4,5,6]
mergeSortedLists([1], [2]) → [1,2]
mergeSortedLists([1,1,1], [1,1]) → [1,1,1,1,1]
mergeSortedLists([5,10], [1,2,3]) → [1,2,3,5,10]