Remove Nth Node From End of List
同じ長さの2つの配列に格納された単方向連結リストが与えられます。ノード i は値 values[i] を持ち、ノード next[i] へリンクしています。-1 はリストの終端を示し、先頭はノード 0 です。ノードはリストの順序どおりに格納されていないため、リンクをたどってください。
リストの末尾から数えて n 番目のノードを削除します。最後のノードは末尾から数えて1番目です。残ったノードの値を、リストの順序で返してください。
関数
- valuesinteger-array
- 各ノードが保持する値
- nextinteger-array
- 各ノードがリンクするノードのインデックス。最後のノードの場合は -1
- ninteger
- 末尾から数えて、削除するノードの位置。1は最後のノードです
- 戻り値integer-array
- リストの順序で残りの値。唯一のノードが削除された場合は空
制約
1 ≤ L ≤ 5000。ここで、Lはvaluesとnextの長さです。-100 ≤ values[i] ≤ 1001 ≤ n ≤ L- 各
next[i]は-1または0からL-1までのノードのインデックスです。 - ノード
0から始まり、リストは各ノードをちょうど1回ずつ訪れ、その後-1に到達します。循環はありません。
例
- 入力
- values = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
- 出力
- [5, 2, 6, 7]
- 説明
- ノード
0からリンクをたどると、ノード0, 2, 4, 1, 3を訪れるので、リストは5, 2, 6, 9, 7となります。末尾から2番目はノード1、値は9で、それを取り除くとリストは5, 2, 6, 7となります。配列の要素values[5-2] = 7は最後のノードであり、削除するノードではありません。
- 入力
- values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
- 出力
- [20, 30, 40]
- 説明
- 4つのノードがあり、
n = 4の場合、末尾から4番目のノードが先頭です。リストはノード1から始まり、20, 30, 40の順になります。
- 入力
- values = [42]next = [-1]n = 1
- 出力
- []
- 説明
- 唯一のノードは、先頭ノードであると同時に最後のノードでもあります。それを削除するとリストは空になるため、答えは
[]です。
提出時に隠しテスト+14件
発展問題
長さを先に数えずに、1回の走査でノードを見つけてリンクを解除できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
リストは前方向にしかたどれず、ノードは末尾からの距離で定義されています。長さが
Lだとわかっている場合、先頭から何番目に位置するでしょうか？また、そのノードを取り除くには、どのノードのリンクを変更する必要がありますか？長さがなくても末尾までの距離を測れます。一方のポインターをもう一方より
n個先に進めてから、2つを一緒に動かします。先行するポインターが最後のノードに立ったとき、後続のポインターは削除するノードの直前に立っています。fastをn回進めます。現在-1なら、削除するノードは先頭なので、リストはnext[0]から始まります。それ以外の場合は、next[fast] != -1の間、slowとfastを一緒に進め、その後next[slow] = next[next[slow]]を設定します。先頭からリストをたどり、値を集めます。
解説
対象は末尾からの距離で定義されますが、単方向連結リストでは前方にしか進めず、末尾の位置がわかるのはそこに到達したときだけです。ノードを削除するには、その直前のノードに位置する必要もあります。リンクを変更するのはそのノードだからです。リストを配列にコピーする方法や、ノード数を数えてからもう一度たどる方法があります。定番の方法では、2つのポインターを n 個分離しておきます。すると、先頭側のポインターが最後のノードに到達したとき、後方のポインターは対象の直前に位置します。以下では、L はノード数を表します。
値を配列にコピーする
考え方
この問題では、ポインターはノードのインデックスです。前に進むには node = next[node] とし、-1 に到達したら末尾を越えたことになります。最初の例では、ノード 0 から進むと 0 → 2 → 4 → 1 → 3 → -1 となります。
末尾から数えるのが難しいのは、リストに位置がないからです。そこで、位置を付けます。一度たどって、各値を配列に追加します。最初の例では、この配列は [5, 2, 6, 9, 7] です。L 個の値を持つ配列では、最後の値はインデックス L-1 にあるので、末尾から n 番目の値はインデックス L-n にあります。この場合は 5-2 = 3、つまり 9 です。これを削除して、[5, 2, 6, 7] を返します。
これは正しく、O(L) 時間で実行できますが、リスト全体をコピーし、リンクには一切触れません。この問題のポイントは、追加メモリ O(1) でリスト自体を編集することです。次の2つの方法では、それを行います。
アルゴリズム
- 空の配列と
node = 0から始めます。 nodeが-1でない間、values[node]を追加し、next[node]に移動します。- インデックス
length - nの要素を削除します。 - 配列を返します。
def removeNthFromEnd(values, next, n):
# Write the values out in list order.
order = []
node = 0
while node != -1:
order.append(values[node])
node = next[node]
# Counting from the end, the n-th value sits at index len(order) - n.
del order[len(order) - n]
return orderノードを数えてから、リンクを解除する
考え方
リストからノードを削除するには、その前のノードのリンクを変更して、削除するノードを飛ばすようにします: next[prev] = next[next[prev]]。削除したノードは配列内に残りますが、先頭からたどっても二度と到達しません。
そこで、prevを見つけます。最初の走査でノード数を数えます。先頭を位置0とすると、対象ノードは位置L-nにあり、その前のノードは位置L-n-1にあるため、先頭からL-n-1ステップ進むと到達します。最初の例ではL = 5、n = 2です。2ステップ進むと0 → 2 → 4となり、ノード4に到達します。このノードはノード1、つまり9につながっています。next[4] = next[1] = 3と設定すると、リストは5, 2, 6, 7となります。
対象ノードの前にノードがない場合があります。つまり、対象が先頭であるn = Lの場合です。その場合、リンクを変更する必要はありません。2つ目の例のように、リストの開始位置は0ではなくnext[0]になります。その後、先頭から走査して答えを集めます。リストを2回走査するコストはおよそ2L回の移動で、答え以外に必要なメモリは整数数個分です。
アルゴリズム
- ノード
0から-1まで進み、ノードの数をLとして数えます。 n == Lの場合、新しい先頭はnext[0]です。- それ以外の場合は、
prevをノード0に設定してから、L-n-1回進め、その後next[prev] = next[next[prev]]を設定します。 - 先頭から順に進み、
values[node]を順番に集めます。
def removeNthFromEnd(values, next, n):
# First pass: count the nodes.
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
head = 0
if n == length:
# The node to remove is the head, so the list starts at its second node.
head = next[0]
else:
# Second pass: stop on the node just before position length - n.
prev = 0
for _ in range(length - n - 1):
prev = next[prev]
next[prev] = next[next[prev]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return resultn個のリンク分離れた2つのポインター
考え方
L が分からなくても、「末尾から n 番目」の位置を測れます。slow を先頭で待たせたまま、fast を n 個先に進めます。その後、両方を一度に 1 個ずつ進めます。間隔は n のままなので、fast が最後のノード（next[fast] == -1、位置 L-1）に来たとき、slow は位置 L-1-n、つまり対象の直前のノードにいます。next[slow] = next[next[slow]] を 1 回実行すれば、対象を取り除けます。
最初の例を見てみましょう。fast は 2 歩進み、0 → 2 → 4 となります。次に両方を進めます。slow が 2 に進む間に fast は 1 に進み、続いて slow が 4 に進む間に fast は 3 に進みます。ノード 3 が最後のノードなので、そこで停止します。next[4] は 9 を持つノード 1 なので、next[4] = next[1] = 3 と設定すると、これを取り除けます。
先頭が対象となるケースは、自然に分かります。n ≤ L なので、fast が先行している間に -1 に到達するのは n = L のときだけで、これはちょうど先頭が対象となる場合です。ノードオブジェクトを使う場合は、先頭の前にダミーノードを置けば、このケースをなくせます。ここでは fast == -1 のチェックが同じ役割を果たします。探索とリンク解除は 1 回の走査で完了します。答えを書き出すにはさらに 1 回走査しますが、これはどの方法でも必要です。
アルゴリズム
fast = 0を設定し、fast = next[fast]を使ってn回移動します。fast == -1の場合、先頭が対象です。新しい先頭はnext[0]です。- それ以外の場合は
slow = 0を設定し、next[fast] != -1の間、両方を移動させます。 next[slow] = next[next[slow]]を設定します。- 先頭からたどり、
values[node]を順番に収集します。
def removeNthFromEnd(values, next, n):
# Send fast n links ahead of slow.
fast = 0
for _ in range(n):
fast = next[fast]
head = 0
if fast == -1:
# Fast fell off the end, so the list has exactly n nodes: remove the head.
head = next[0]
else:
# Move both, keeping the gap. When fast stands on the last node,
# slow stands just before the node to remove.
slow = 0
while next[fast] != -1:
slow = next[slow]
fast = next[fast]
next[slow] = next[next[slow]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result
落とし穴と境界ケース
誤答の多くは、追従ポインターをどこで止めるか、そして先頭ノードを削除するケースに起因します。
- 配列インデックス
L-nの要素を削除すること。ノードはリスト順に格納されていないため、そのインデックスが指すのは通常、別のノードです。最初の例では、values[3] = 7は最後のノードであり、9ではありません。 next[fast] == -1のときではなく、fast == -1のときに止めること。これではslowが1つ先に進み、対象ノードそのものを指してしまいます。単方向連結リストでは、そのノード自身からノードを連結解除することはできません。- 先頭ノードの場合を考慮し忘れること。
n = Lのとき、先頭から進めた後のfastは-1になり、多くの言語ではnext[fast]を読み取ろうとするとクラッシュします。Pythonではエラーにならずにnext[-1]を読み取り、誤ったリストを返すため、間違いに気づきにくくなります。 next[slow] = next[slow] + 1やslow + 2で連結解除しようとすること。リスト内で隣り合うノードが配列内でも隣り合っているとは限りません。対象ノードの次のノードへ進むには、next[next[slow]]を使うしかありません。- 先頭ノードを削除した後、ノード
0から答えを集めること。最後にリストをたどるときは、新しい先頭ノードから始めてください。 - 配列のインデックスが1から始まるLuaとRで、オフセットを考慮し忘れること。ノードのインデックスは0始まりのままにして、
next[node + 1]を読み取ってください。RubyとRではnextという語が予約されているため、スターターコードではパラメーターにnext_という名前を付けています。
よくある質問4
連結リストの末尾から n 番目のノードを、1 回の走査で削除するにはどうすればよいですか？
n 個分の間隔を空けて 2 つのポインターを使います。1 つ目のポインターを n 個先のノードまで進めてから、1 つ目のポインターが最後のノードに来るまで、両方を一緒に進めます。2 つ目のポインターは削除するノードの直前にあるので、そのリンクをそのノードの次に向けます。先行している間に 1 つ目のポインターがリストの末尾を越えた場合、削除するノードは先頭です。
この問題の解法では、なぜダミーノードを使うのですか？
ノードを削除するとは、その直前のノードのリンクを変更することです。head の直前にはノードがありません。head の前にダミーノードを置くと、head を含むすべてのノードに先行ノードができるため、1行のリンク解除処理ですべてのケースに対応できます。答えはその後、ダミーノードの次のノードから始まります。n ステップ後に先頭のポインターがリストの末尾を越えたかどうかを確認すれば、余分なノードを追加せずに同じケースに対応できます。
末尾から n 番目のノードを削除する場合の時間計算量と空間計算量は何ですか？
L個のノードからなるリストでは、対象の位置を知るには末尾までたどる必要があるため、時間計算量はO(L)です。最初に数える方法と2つのポインターを使う方法は、どちらも追加メモリをO(1)使用します。値を配列にコピーする方法では、O(L)使用します。
2ポインター解法は、最初に長さを数える方法よりも速いですか？
大きな差はありません。どちらも O(L) で、2つのポインターを合わせた移動回数も、2回たどる場合とほぼ同じです。本当の利点は、あらかじめ長さを知る必要がないことです。そのため、リストが一度しか読み取れないストリームとして届く場合にも、この方法が使えます。面接官が通常求めるのは、この1回の走査です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def removeNthFromEnd(values, next, n):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
values = [5, 9, 2, 7, 6] next = [2, 3, 4, -1, 1] n = 2
期待値
[5, 2, 6, 7]