Reorder List
同じ長さの2つの配列に格納された単方向リンクリストが与えられます。ノード i は値 values[i] を保持し、ノード next[i] へのリンクを持ちます。-1 はリストの終端を示し、先頭ノードは 0 です。ノードはリストの順序どおりに格納されていないため、リンクをたどってください。
リストの順序に従ってノードを L0, L1, ..., Lk と呼びます。リストを L0, Lk, L1, Lk-1, L2, Lk-2, ... の順になるように並べ替えます。つまり、最初のノード、最後のノード、2番目のノード、最後から2番目のノード、という順に並べます。新しい順序で値を返してください。
関数
- nextinteger-array
- 各ノードがリンクするノードのインデックス、または最後のノードの場合は -1
- valuesinteger-array
- 各ノードが保持する値
- 戻り値integer-array
- 並べ替え後のリストの順序における値
制約
1 ≤ n ≤ 4000。ここで、nはnextとvaluesの長さです。-1000 ≤ values[i] ≤ 1000- 各
next[i]は-1、または0からn-1までのノードインデックスです。 - ノード
0から始まり、リストはすべてのノードをちょうど1回ずつ訪れ、その後-1に到達します。循環はありません。
例
- 入力
- next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
- 出力
- [1, 5, 2, 4, 3]
- 説明
- ノード
0からリンクをたどると、リストは1, 2, 3, 4, 5となります。最初、最後、2番目、最後から2番目の順にすると1, 5, 2, 4となり、中央の値3は最後になります。
- 入力
- next = [2, 3, 1, -1]values = [10, 30, 20, 40]
- 出力
- [10, 40, 20, 30]
- 説明
- リストはノード
0, 2, 1, 3を順にたどり、10, 20, 30, 40を読み取ります。最初と最後は10, 40で、その後、内側のペアは20, 30です。
- 入力
- next = [-1]values = [7]
- 出力
- [7]
- 説明
- ノードが1つのリストでは移動するものがないため、答えは
[7]です。
発展問題
追加メモリ O(1) でリンク自体を並べ替えることはできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
1, 2, 3, 4, 5, 6に対する目標の順序を書いてください。リストの前半から来るノードはどれですか。また、後半のノードはどの順序で現れますか？後半部分は逆順で表示されます：
6, 5, 4。後半部分が逆順になっていれば、答えはそれぞれのリストからノードを1つずつ交互に取り出して結合した2つのリストになります。1つのリンクずつ進む遅いポインターと、2つずつ進む速いポインターを使って、中央を見つけます。中央の後でリストを切り分け、リンクの向きを変えて後半を逆順にしたら、2つの部分をノードごとに交互に織り合わせます。
解説
新しい順序では先頭と末尾が交互に並びますが、単方向連結リストは前方にしかたどれません。この処理を、標準的なリスト操作3つに分けましょう。スロー／ファストポインターで中央を見つけ、後半を反転し、2つの半分を1ノードずつ交互に織り合わせます。
末尾を一度に1つのノードずつ前に進める
考え方
ここでポインターはノードのインデックスであり、次へ進むには node = next[node] とします。最初のノードの次には最後のノードが来るので、最後のノードを外して現在のノードの後に挿入し、その後さらに2つ先のノードで同じ操作を繰り返します。1, 2, 3, 4, 5 の場合、結果は 1, 5, 2, 3, 4 となり、次に 1, 5, 2, 4, 3 となります。現在のノードの後に続くノードが2つ未満になったら終了します。
最後のノードの1つ前のノードを見つけるには、毎回末尾までたどる必要があります。たどる距離は1回ごとに2ノードずつ短くなり、移動の合計はおよそ n²/4 回です。4000ノードなら400万回です。
アルゴリズム
cur = 0を設定します。curの後ろに少なくとも2つのノードがある間、next[next[before]] == -1となるまでcurからbeforeをたどります。これにより、tail = next[before]が最後のノードになります。next[before] = -1で接続を外し、その後挿入します。next[tail] = next[cur]およびnext[cur] = tailとします。curをnext[tail]に移動し、繰り返します。- ノード
0からたどり、値を収集します。
def reorderList(next, values):
cur = 0
# While at least two nodes follow cur, move the last node right after cur.
while next[cur] != -1 and next[next[cur]] != -1:
before = cur
while next[next[before]] != -1: # find the node before the tail
before = next[before]
tail = next[before]
next[before] = -1
next[tail] = next[cur]
next[cur] = tail
cur = next[tail]
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return result値をコピーし、両端から読み取る
考え方
配列は1ステップで最後の要素に到達します。値をリストの順序でコピーします。最初の例では[1, 2, 3, 4, 5]です。次に、先頭からlo、末尾からhiを読み取り、loを取り、hiを取り、lo < hiの間、両方を内側へ移動します。これにより1, 5, 2, 4となります。長さが奇数の場合は、中央の3で両方が出会い、これが最後になります。
これは時間計算量がO(n)、追加メモリがO(n)で、リンクは決して変わりません。
アルゴリズム
- ノード
0からたどり、各値をinOrderに追加します。 lo = 0に設定し、hiを最後のインデックスに設定します。lo < hiの間、inOrder[lo]とinOrder[hi]を追加してから、loを増やし、hiを減らします。lo == hiの場合は、中央の値を追加します。
def reorderList(next, values):
# Write the values out in list order.
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
# Take from the front and the back in turn.
result = []
lo, hi = 0, len(in_order) - 1
while lo < hi:
result.append(in_order[lo])
result.append(in_order[hi])
lo += 1
hi -= 1
if lo == hi: # odd length: the middle value comes last
result.append(in_order[lo])
return result中央を見つけ、後半を逆順にして、交互に組み合わせる
考え方
1, 2, 3, 4, 5, 6の場合、答えは1, 6, 2, 5, 3, 4です。前半の1, 2, 3を順番に並べ、逆順に読んだ後半の4, 5, 6と交互に並べます。つまり、リストを中央で分割し、後半を逆順にして、交互に組み合わせます。
slowはリンクを1つ進み、fastは2つ進むため、slowは前半の最後のノード、つまりノード数が5個でも6個でも3で止まります。その後ろで分割すると、ノード数が奇数の場合、前半に余分なノードが1つ含まれ、そのノードが答えの最後になります。後半がなくなるまで、両方の半分から交互に1つずつノードを取り出して組み合わせます。
各ノードに触れる回数は定数回で、メモリは少数のインデックス分だけです。Rではリンクベクトルを最初に変更するときにコピーするため、メモリ使用量はO(n)です。
アルゴリズム
next[fast]とnext[next[fast]]が-1でない間、slowを1つ、fastを2つ進めます。second = next[slow]を設定し、次にnext[slow] = -1を設定します。secondから始まるリストを反転します。その新しい先頭はprevです。- 交互につなぎます。
secondが-1でない間、firstをsecondにつなぎ、secondを以前のnext[first]につないでから、両方を進めます。 - ノード
0からたどり、値を集めます。
def reorderList(next, values):
# 1. Find the middle: slow stops on the last node of the first half.
slow = fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
# 2. Reverse the second half.
prev = -1
while second != -1:
after = next[second]
next[second] = prev
prev = second
second = after
# 3. Weave: one node from the front half, one from the reversed back half.
first, second = 0, prev
while second != -1:
first_after, second_after = next[first], next[second]
next[first] = second
next[second] = first_after
first, second = first_after, second_after
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return result
落とし穴と境界ケース
- リストを途中で切らないこと。
next[slow] = -1がないと、前半が後半を指したままになり、交互に組み合わせた後、リストがループしてしまいます。 - リンクを保存する前に上書きしないこと。反転と交互に組み合わせる処理では、まず
next[node]を変数に読み込んでください。そうしないと、リストの残りが失われます。 - 前半が終わるまで交互に組み合わせないこと。長さが奇数の場合、そのループはもう一度実行され、
secondが-1の状態でnext[-1]を読み込んでしまいます。 - 配列の順序をリストの順序として読まないこと。最初の例では、
valuesは[1, 3, 5, 2, 4]ですが、リストは1, 2, 3, 4, 5の順です。 - LuaとRでは配列のインデックスは1から始まります。ノードのインデックスは0始まりのままにして、
next[node + 1]を読み込んでください。
よくある質問3
リストの後半を逆順にするのはなぜですか？
答えは後半を最後のノードから最初のノードへと読み取りますが、単方向連結リストは前方にしか進めません。後半を1回、O(n)で反転すると、マージ時に両方の半分を前方へたどれます。
Reorder List の時間計算量は何ですか？
インプレースメソッドはO(n)時間、追加メモリO(1)で実行できます。中央を見つける処理、反転処理、交互に組み合わせる処理では、それぞれ各ノードを定数回だけ訪問します。値を配列にコピーする方法もO(n)時間ですが、O(n)メモリが必要です。また、末尾を一度に1ノードずつ前に進める方法はO(n²)です。
リストのノード数が偶数の場合、中央はどこですか？
def reorderList(next, values):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
next = [3, 4, -1, 1, 2] values = [1, 3, 5, 2, 4]
期待される出力
[1, 5, 2, 4, 3]