Sort List
同じ長さの2つの配列に格納された単方向連結リストが与えられます。ノード i は値 values[i] を持ち、ノード next[i] へのリンクを持ちます。-1 はリストの末尾を示し、先頭ノードは 0 です。ノードはリストの順序どおりには格納されておらず、配列には、ノード 0 からたどっても到達しない残存ノードが含まれている場合もあります。リンクがリスト内のノードを指していても、それらはリストの一部ではありません。
値の非減少順にリストを並べ替え、その順序でノードの値を返してください。
関数
- nextinteger-array
- 各ノードがリンクするノードのインデックス、または最後のノードの場合は -1
- valuesinteger-array
- 各ノードが保持する値
- 戻り値integer-array
- リストのノードの値を小さい順に
制約
1 ≤ n ≤ 4000。ここで、nはnextとvaluesの長さです。-1000 ≤ values[i] ≤ 1000- 各
next[i]は-1、または0からn-1までのノードインデックスです。 - ノード
0から開始すると、同じノードを2回訪れることなく、リストは-1に到達します。 - ノード
0からの走査で到達できないノードは、リストの一部ではありません。それらのnextエントリはどこを指していてもかまいません。
例
- 入力
- next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
- 出力
- [1, 2, 3, 4, 5]
- 説明
- ノード
0からの探索ではノード0, 3, 2, 4, 1を訪れるため、リストは4, 2, 3, 5, 1となります。これを並べ替えると、1, 2, 3, 4, 5です。
- 入力
- next = [2, 0, -1, -1]values = [6, 9, -2, 5]
- 出力
- [-2, 6]
- 説明
- リストは
0 → 2で、6, -2と読み取れます。ノード1と3は先頭から到達できないため、ノード1がノード0にリンクしているにもかかわらず、それらの値9と5は含まれません。
- 入力
- next = [1, 2, 3, -1]values = [3, -1, 3, -1]
- 出力
- [-1, -1, 3, 3]
- 説明
- リストは
3, -1, 3, -1と読み取れます。同じ値は、出現した回数だけ答えに残ります：-1, -1, 3, 3。
発展問題
値をコピーして取り出すことなく、ノードをつなぎ直して O(n log n) 時間でソートできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
任意の位置にジャンプする必要があるのはどのソートアルゴリズムで、入力を前方に進むだけなのはどのアルゴリズムでしょうか？連結リストは後者に適しています。
2つのソート済みリストを1つにまとめるのに、追加のメモリは必要ありません。ノードをつなぎ直し、常に先頭の2つの値のうち小さい方を選びます。リストをソート済みの2つの半分に分割できれば、1回のマージで処理が完了します。
遅いポインターと速いポインターを使って中央を見つけ、そこでリストを切り分けます。それぞれの半分を同じ方法でソートし、すでにソート済みの単一ノードになるまで続けます。次に、ソート済みの2つの半分をマージし、新しい先頭ノードを返します。
解説
クイックソートとヒープソートはランダムアクセスに依存しますが、単方向連結リストは前方にしか進めません。マージソートが適しています。リストを中央で分割する処理も、2つのソート済みリストをマージする処理も、どちらも前方に進むため、リンク自体を O(n log n) でソートできます。ここで n は配列の長さです。
値を配列にコピーして並べ替える
考え方
リストは、ノード 0 から始めて node = next[node] をたどり、-1 までに訪れるノードです。それらの値を新しい配列に集め、組み込みのソートで並べ替えて返します。values を直接ソートすることはできません。2つ目の例では、リストに含まれない 9 と 5 が入っているためです。
たどる処理は O(n)、ソートは O(n log n) で、追加メモリは O(n) です。リスト自体には一切手を加えません。そのため、面接官は次のアプローチについて尋ねます。
アルゴリズム
- 空の配列と
node = 0から始めます。 nodeが-1でない間、values[node]を追加し、next[node]に移動します。- 配列を昇順に並べ替えて返します。
def sortList(next, values):
# Collect the values of the nodes on the list, then sort them.
on_list = []
node = 0
while node != -1:
on_list.append(values[node])
node = next[node]
on_list.sort()
return on_listリンクのマージソート
考え方
1つ進む遅いポインターと2つ進む速いポインターを使えば、1回の走査で中央を見つけられます。2つのソート済みリストのマージに必要なのは先頭のノードだけです。小さい方を取り、先へ進みます。どちらの処理にも2つ目の配列は必要ありません。
最初の例では、slow は 3 で止まり、そのリンクを切ると 4, 2, 3, 5, 1 は 4, 2, 3 と 5, 1 に分かれます。これらをソートすると 2, 3, 4 と 1, 5 になり、マージでは 1, 2, 3, 4 を取り、その後、残った 5 をつなぎます。
分割の各レベルでは、すべてのノードに定数回アクセスします。また、レベル数は約 log n なので、時間計算量は O(n log n) です。追加で必要なメモリは再帰スタックだけで、4000個のノードなら深さは約12回の呼び出しです。
アルゴリズム
- リストにノードが1つしかない場合（
next[head] == -1）、headを返します。 slow = head、fast = next[head]として開始します。fastとnext[fast]が-1でない間、slowを1リンク、fastを2リンク進めます。second = next[slow]とし、next[slow] = -1で切り離します。- 両方の半分を再帰的にソートします。マージするには、片方が空になるまで、小さい方の先頭ノードを
tailの後ろにつなぎ、その後、もう片方の残りをつなぎます。 - 返されたheadからたどり、値を集めます。
def sortList(next, values):
def merge(a, b):
# Splice two sorted lists into one; on a tie the node from a goes first.
head = tail = -1
while a != -1 and b != -1:
if values[b] < values[a]:
node, b = b, next[b]
else:
node, a = a, next[a]
if tail == -1:
head = node
else:
next[tail] = node
tail = node
next[tail] = a if a != -1 else b # attach whatever is left
return head
def sort(head):
if next[head] == -1: # one node is already sorted
return head
# slow stops on the last node of the first half
slow, fast = head, next[head]
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
return merge(sort(head), sort(second))
result = []
node = sort(0)
while node != -1:
result.append(values[node])
node = next[node]
return result
落とし穴と境界ケース
values配列全体をソートする。2つ目の例では、リストにない9と5が持ち込まれる。- 先頭で
fastを開始する。ノードが2つある場合、slowは2つ目のノードに到達し、切断すると後半が空になり、再帰がいつまでも縮小しない。 - 切断処理
next[slow] = -1を忘れる。すると前半が後半につながったままになり、両方の呼び出しが重複するリストをソートする。 - もう一方が尽きたときに、片方の残りを落とす。そのノードは結果から消えてしまう。
- Lua と R では配列は1から始まる。ノードのインデックスは0ベースのままにして、
next[node + 1]を読み取る。R版はリンク配列を1回コピーするため、追加メモリを O(n) 使用する。
よくある質問3
連結リストをソートする最適な方法は何ですか？
マージソート。中央で分割し、両方の半分をソートしてマージする処理は、すべてリストを前方にたどります。単方向連結リストがサポートする方向は前方のみです。実行時間は O(n log n) で、既存のノードをつなぎ直します。
連結リストでは、なぜマージソートがクイックソートよりも好まれるのですか？
クイックソートは要素をつなぎ直してリストを分割できますが、適切なピボットを選ぶにはランダムアクセスが必要です。また、先頭をピボットにすると、ソート済みリストの計算量は O(n²) になります。マージソートは常に半分に分割するため、どのような入力でも O(n log n) のままです。
連結リストを O(n log n) 時間、O(1) メモリでソートできますか？
はい、ボトムアップのマージソートを使います。隣り合う長さ1のランをマージし、次に長さ2、次に長さ4と、1つのランがリスト全体を覆うまで続けます。線形パスはlog n回で、必要なメモリはノードのインデックスがいくつかだけです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def sortList(next, values):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
next = [3, -1, 4, 2, 1] values = [4, 1, 3, 2, 5]
期待される出力
[1, 2, 3, 4, 5]