Merge Two Sorted Lists
同じ長さの2つの配列にそれぞれ格納された、2つの単方向連結リストが与えられます。1つ目のリストでは、ノード i が値 values1[i] を持ち、ノード next1[i] につながっています。2つ目のリストも同様に、next2 と values2 を使います。どちらのリストも -1 で終わり、先頭ノードは 0 です。ノードはリストの順序どおりに格納されていないため、リンクをたどってください。
各リストは、リンクに沿って値が非減少順に並んでいます。2つのリストを1つのソート済みリストにマージし、値を順番に返してください。
関数
- next1integer-array
- 最初のリストの各ノードがリンクしているノードのインデックス。最後のノードの場合は -1
- values1integer-array
- 最初のリストの各ノードが保持する値
- next2integer-array
- 2つ目のリストの各ノードがリンクしているノードのインデックス。最後のノードの場合は-1
- values2integer-array
- 2番目のリストの各ノードが保持する値
- 戻り値integer-array
- マージされたリストの値（順番どおり）
制約
1 ≤ L1 ≤ 2000。ここで、L1はnext1とvalues1の長さです。1 ≤ L2 ≤ 2000。ここで、L2はnext2とvalues2の長さです。-1000 ≤ values1[i], values2[j] ≤ 1000-
next1の各エントリは-1または最初のリストのノードインデックスであり、next2の各エントリは-1または2番目のリストのノードインデックスです。 - ノード
0から始めると、各リストはそのすべてのノードをそれぞれ1回だけ訪問し、その後-1に到達します。サイクルはありません。 - リンクに沿って、各リストは非減少順に並んでいます。
例
- 入力
- next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
- 出力
- [1, 2, 3, 4, 6, 7, 9]
- 説明
- リンクをたどると、最初のリストはノード
0, 2, 1を訪れ、1, 4, 6を読み取ります。2つ目のリストは2, 3, 7, 9を読み取ります。毎回先頭の小さい方を取ると、1, 2, 3, 4, 6, 7, 9になります。
- 入力
- next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
- 出力
- [-3, 0, 0, 5]
- 説明
- 最初のリストは
-3, 0, 5で、2つ目は単一の値0です。どちらの0も結果に残るため、値は4つになります。
- 入力
- next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
- 出力
- [1, 2, 3, 8, 10]
- 説明
- 2つ目のリストは
1, 2, 3で、すべて最初のリストの先頭にある8より小さい値です。2つ目のリスト全体が先に来て、その後に8, 10が続きます。
発展問題
k 個のソート済みリストを、ノードの総数が N のとき、O(N log k) 時間でマージできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
両方のリストはすでにソートされています。マージ後のリストの最小値の候補となる値は、どの2つだけですか？
各リストの最初の未使用ノードにポインターを1つずつ置きます。2つの値のうち小さい方が次に進み、そのポインターだけを前に進めます。一方のリストが尽きたら、もう一方に残っている要素はすでに順番どおりです。
2つ目のリストのノードには、1つ目のリストのノードに続く番号を付け、1つのリンク配列で両方を扱えるようにし、先頭にダミーノードを追加します。マージしたリストの最後のノードである
tailを保持し、そのリンクを先頭のノードのうち値が小さい方に向けて、前に進みます。最後に、ダミーノードからたどって値を集めます。
解説
どちらのリストもソートされているため、残っている最小の値は常にどちらかのリストの先頭にあります。2つの先頭を比較し、小さいほうを結果につなげて、そのリストで1つ先に進みます。N = L1 + L2 個の値をすべてソートする方法もありますが、順序を活用せず、O(N log N) のコストがかかります。
すべての値を1つの配列に入れて並べ替えます
考え方
マージしたリストはすべてのN値を並べ替えたものなので、両方の値の配列を1つにまとめて並べ替えます。配列内のノードの順序は重要ではありません。ソートによってすべての値が配置されるためです。N ≤ 4000なら十分高速ですが、ソートにはO(N log N)回の比較が必要です。一方、マージに必要な比較は最大でもN-1回であり、リンクには一切触れません。これこそがこの問題で試されるスキルです。
アルゴリズム
values1とvalues2を1つの配列にコピーします。- 配列を非減少順に並べ替えます。
- それを返します。
def mergeTwoLists(next1, values1, next2, values2):
# Sorting puts every value in its place without following a single link.
return sorted(values1 + values2)ダミーヘッドの後ろにノードをつなぎます
考え方
ここでポインターはノードのインデックスです。両方のリストのノードを1本の連結リストにまとめるには、共通の番号を割り当てます。リスト2のノード j はノード L1+j となり、そのリンクも同じだけずらします。番号 L1+L2 のダミーノードを、結果の先頭に置きます。
a と b は各リストの未使用の先頭ノードを指し、tail はマージ後の連結リストの末尾を指すようにします。各ステップで、tail を値の小さいほうの先頭ノードにつなぎ、そのポインターと tail を進めます。一方のリストが尽きたら、もう一方の残りはすでにソート済みでつながっているため、1回の代入で接続できます。最初の例では、リスト2はノード 3 から 6 になります。ノード 0, 3, 6, 2, 1 の後、リスト1が空になり、link[tail] = 4 によって 7, 9 がつながります。
各ノードをつなぐのは最大1回です。時間計算量は O(N) です。共有リンク配列のメモリ計算量は O(N) ですが、ノードオブジェクトならメモリは不要です。
アルゴリズム
- 1つのリンク配列を作成します。
next1、次にL1だけシフトしたnext2（-1はそのままにします）、そしてダミーのL1+L2に対する-1です。対応する値も作成します。 a = 0、b = L1に設定し、tailをダミーに設定します。aもbも-1でない間、tailを小さい方（同値ならa）にリンクし、そのポインターを進めて、tailをその位置に移動します。aとbのうち-1でない方にtailをリンクします。link[dummy]から-1までたどり、値を集めます。
def mergeTwoLists(next1, values1, next2, values2):
n1 = len(next1)
n2 = len(next2)
# One node space: list 2's node j becomes node n1 + j, and node n1 + n2 is a
# dummy that sits in front of the merged list.
link = list(next1) + [j + n1 if j != -1 else -1 for j in next2] + [-1]
value = list(values1) + list(values2)
dummy = n1 + n2
tail = dummy # the last node of the merged list so far
a = 0 # the first unused node of list 1
b = n1 # the first unused node of list 2
while a != -1 and b != -1:
if value[a] <= value[b]:
link[tail] = a # splice a in after the tail
a = link[a]
else:
link[tail] = b # splice b in after the tail
b = link[b]
tail = link[tail]
# One list ran out. The rest of the other one is sorted and linked already.
link[tail] = a if a != -1 else b
merged = []
node = link[dummy]
while node != -1:
merged.append(value[node])
node = link[node]
return merged
落とし穴と境界ケース
- インデックス順に配列をマージすること。ノードはシャッフルされて格納されているため、
values1自体はソートされていません。最初の例では[1, 6, 4]です。ソートされているのは、ノード0からたどった場合だけです。 - 残りを忘れてしまうこと。一方のリストが尽きるとループは停止しますが、もう一方のリストの残りを捨てると、最初の例では最大値の
7, 9が失われます。 - 誤ったポインター、または両方のポインターを進めること。進めるのは、ノードを取り出したリストだけです。
- 2つの番号体系を混同すること。リスト2のノード
2は、リスト1のノード2ではありません。リスト2のインデックスとリンクにはL1を加え、-1はそのままにします。
よくある質問3
2つのソート済みリストをマージする時間計算量はどのくらいですか？
O(L1 + L2)です。比較のたびに1つのノードを配置し、同じノードを2回配置することはありません。ノードオブジェクトを使う場合、マージで必要な追加メモリはO(1)です。リンクを変更するだけだからです。ここで使用している配列の場合、共有リンク配列にO(L1 + L2)のメモリが必要です。
連結リストをマージするときにダミーノードを使うのはなぜですか？
これがない場合、まだその後ろにつなぐ末尾がないため、結果の最初のノードには別個のコードが必要です。ダミーはプレースホルダーの先頭ノードなので、最初のノードも他のノードと同じ方法でつなげます。最後にダミーの次のノードを返すと、プレースホルダーはなくなります。
2つのソート済みリストは、再帰的にマージするべきですか、それとも反復的にマージするべきですか？
再帰版は短く、より小さい先頭要素が残りすべてをマージした結果につながります。しかし、ノードごとに1つのスタックフレームを使うため、言語によっては数千個のノードからなるリストでスタックがオーバーフローすることがあります。末尾ポインターを使った反復ループなら、同じ処理を一定のスタック領域で実行できます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def mergeTwoLists(next1, values1, next2, values2):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
next1 = [2, -1, 1] values1 = [1, 6, 4] next2 = [3, 2, -1, 1] values2 = [2, 7, 9, 3]
期待される出力
[1, 2, 3, 4, 6, 7, 9]