Reverse Linked List
配列 next に格納された単方向連結リストが与えられます。ノード i はノード next[i] にリンクし、-1 はリストの終端を示し、先頭はノード 0 です。ノードはリストの順序どおりには格納されていないため、リンクをたどってください。
すべてのリンクの向きを反転してリストを逆順にします。これにより、元の最後のノードが先頭になり、ノード 0 は最後のノードとなって -1 にリンクします。入力と同じ長さの、更新後の next 配列を返してください。
関数
- nextinteger-array
- 各ノードがリンクするノードのインデックス。最後のノードの場合は -1
- 戻り値integer-array
- 逆順にしたリストの次の配列
制約
1 ≤ next.length ≤ 5000- 各
next[i]は-1または0からnext.length-1までのノードインデックスです。 - ノード
0から始まり、リストは各ノードをちょうど1回ずつ訪れた後、-1に到達します。循環はありません。
例
- 入力
- next = [1, 2, 3, -1]
- 出力
- [-1, 0, 1, 2]
- 説明
- リストは
0 → 1 → 2 → 3です。逆順にすると3 → 2 → 1 → 0なので、ノード3は2に、ノード2は1に、ノード1は0に、そしてノード0は-1にリンクします。
- 入力
- next = [2, -1, 3, 1]
- 出力
- [-1, 3, 0, 2]
- 説明
- リストは
0 → 2 → 3 → 1で、逆順にすると1 → 3 → 2 → 0です。各ノードのインデックスに新しいリンクを書き込むと、[-1, 3, 0, 2]になります。配列自体を逆順にすると[1, 3, -1, 2]となり、これは同じものではありません。
- 入力
- next = [-1]
- 出力
- [-1]
- 説明
- 1つのノードはそれ自身が逆順です。先頭であり末尾でもあり、引き続き
-1にリンクしています。
提出時に隠しテスト+11件
発展問題
リストのうち、位置 left と位置 right の間の部分だけを逆順にして、その前後のノードはそのままにできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべてのリンク
a → bはb → aに変える必要があります。あるノードに立っているとき、そのリンクの向きを反転させるには何を知っている必要がありますか？来た元のノードが必要なので、前のノードを保持しながらリストをたどります。しかし、
next[node]を上書きすると、進む先がなくなってしまいます。何かを変更する前に保存してください。prev = -1とnode = 0から始めます。nodeが-1でない間、next[node]を保存し、next[node]をprevに設定してから、prevをnodeに、nodeを保存した値に移します。nextを返します。
解説
リストを反転しても、ノードが移動するわけではありません。各リンクの向きを変えるだけです。ただし、ノードのリンクはリストの残りの部分にたどり着く唯一の方法なので、上書きした瞬間に、その先のすべてが失われます。先に順序を書き留めておくか、リンクの向きを変える前に進む先を保存する3つのポインターを使って、一度たどればこの問題を避けられます。
順序を書き留めてから、リンクをつなぎ直す
考え方
この問題では、ポインターはノードのインデックスであり、次に進む操作はnode = next[node]です。ノード0から始めて-1に到達するまでたどり、通過したすべてのノードを書き留めます。2つ目の例では、その順序は[0, 2, 3, 1]になります。
逆順のリストでは、各ノードはその順序で直前にあったノードにつながります。1は3に、3は2に、2は0につながります。順序の最初のノード、つまり元の先頭ノードには直前のノードがないため、-1につながります。これらのリンクを新しい配列に格納して返します。
各リンクは新しい配列に書き込まれるため、まだ必要な値が上書きされることはなく、この方法は間違えにくいです。計算時間はO(n)で、順序と新しい配列のためにO(n)の追加メモリを使います。
アルゴリズム
- ノード
0から-1まで進み、各ノードをorderに追加します。 - 同じ長さの新しい配列を作成します。
order[0]のエントリーを-1に設定します。- すべての
k ≥ 1について、order[k]のエントリーをorder[k-1]に設定します。 - 新しい配列を返します。
def reverseList(next):
order = []
node = 0
while node != -1:
order.append(node)
node = next[node]
reversed_next = [0] * len(next)
reversed_next[order[0]] = -1 # the old head ends the new list
for k in range(1, len(order)):
reversed_next[order[k]] = order[k - 1]
return reversed_nextリンクを1回の処理で逆順にする
考え方
元のノードを覚えておけば、そのノードに到達した瞬間に各リンクの向きを変えられます。前のノードである prev を保持します。古い先頭ノードが最後のノードになるため、初期値は -1 です。node において、リンク next[node] は前方を指しています。それを prev に設定して、後方を指すようにします。
この書き込みによって前方へ進む唯一の手段が失われるため、まず3つ目の変数 after = next[node] に保存します。次にリンクの向きを変え、両方のポインターを1つ進めます。prev = node、node = after です。どの時点でも、通過済みのノードは prev を先頭とする逆順のリストを形成し、先にあるノードは node から始まる未処理の残りです。node が -1 に達すると、すべてのリンクの向きが変わり、prev が新しい先頭ノードになります。
2つ目の例では、ポインターはノード 0, 2, 3, 1 を順に進み、next[0] = -1、next[2] = 0、next[3] = 2、next[1] = 3 と書き込みます。各ノードを1回ずつ訪れるため、時間計算量は O(n) で、使用するメモリは3つの整数だけなので O(1) です。
アルゴリズム
prev = -1とnode = 0を設定します。nodeが-1でない間、after = next[node]を保存します。next[node] = prevを設定します。- 次に進みます:
prev = node、その後node = after。 nextを返します。
def reverseList(next):
prev = -1 # the node behind the current one; the old head will point to -1
node = 0
while node != -1:
after = next[node] # save the rest of the list before cutting the link
next[node] = prev
prev = node
node = after
return next
落とし穴と境界ケース
ここでのバグのほとんどは、3つの代入の順序、またはリストの両端に関するものです。
- 保存する前に
next[node]を上書きしてしまう。next[node] = prevの後では、元の前方リンクが失われ、走査は次のノードへ進まずに後戻りします。 prevを-1以外の値で初期化する。元の先頭ノードは新しいリストの末尾にならなければなりません。0で初期化すると、ノード0が自分自身にリンクします。- リンクではなく配列を逆順にする。ノードはリストの順序で格納されておらず、答えではすべてのノードがそれぞれのインデックスにとどまり、変わるのは値だけです。
[2, -1, 3, 1]を逆順にすると[1, 3, -1, 2]になり、[-1, 3, 0, 2]にはなりません。 next[node] != -1を条件にしたループで、最後のノードより1つ手前で停止する。最後のノードのリンクも反転させる必要があるため、node != -1の間ループします。- 長いリストを再帰で反転する。5000個のノードを持つリストでは、5000回のネストした呼び出しが必要になり、Pythonの上限である1000回を超えます。
- 配列のインデックスが1から始まるLuaとRで、オフセットを忘れる。ノードのインデックスは0始まりのままにし、
next[node + 1]を読み取ります。RubyとRではnextが予約語なので、それらのスターターコードではパラメーター名にnext_を使っています。
よくある質問4
連結リストをその場で逆順にするにはどうすればよいですか？
2つのポインターを使ってリストをたどります。prevは何もない状態から、nodeは先頭から開始します。各ノードで次のノードを保存し、そのリンクをprevに向けてから、prevとnodeをそれぞれ1つ先に進めます。nodeがなくなると、prevが反転したリストの先頭になります。
連結リストを反転する時間計算量と空間計算量はどれくらいですか？
反復版は各ノードを1回ずつ訪問し、時間計算量はO(n)で、3つのポインターを保持するため、追加の空間計算量はO(1)です。先に順序を配列にコピーする方法も時間計算量はO(n)ですが、追加の空間計算量としてO(n)が必要です。再帰版は呼び出しスタックにO(n)の空間を使用します。
連結リストを再帰的に反転できますか？
はい。head の後ろをすべて逆順にし、次に head の古い next ノードから head へ戻るようにして、head のリンクを何も指さない状態にします。読みやすいですが、ノードごとにネストした呼び出しを1回行うため、長いリストではコールスタックがあふれる可能性があります。Python はデフォルトで呼び出し回数を1000回に制限しており、5000個のノードからなるリストではこれを超えます。
連結リストを逆順にするには、なぜ3つのポインターが必要なのでしょうか？
ノードのリンクの向きを変えるには、そのノード自身とその前のノードが必要です。つまり、ポインターが2つ必要です。リンクの向きを変えるとリストの残りの部分への唯一の参照が消えてしまうため、3つ目のポインターにはその後のノードを保持します。これがなければ、走査を続けられません。
Python
def reverseList(next):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
next = [1, 2, 3, -1]
期待値
[-1, 0, 1, 2]