Reverse Nodes in k-Group
単方向連結リストは、同じ長さの2つの配列に格納されています。ノード i は values[i] を保持し、ノード next[i] につながっています。-1 はリストの終端を示し、先頭ノードは 0 です。ノードは任意の順序で格納されている場合があるため、配列の順序ではなく、リンクをたどってください。
リストを k 個のノードごとのグループに分けて反転してください。最初の k 個のノードを反転し、次の k 個も同様に反転します。最後のグループが k 個未満の場合は、順序をそのままにします。新しいリストの順序で値を返してください。
関数
- nextinteger-array
- 各ノードがリンクするノードのインデックス、または最後のノードの場合は -1
- valuesinteger-array
- 各ノードが保持する値
- kinteger
- 反転する各グループ内のノード数
- 戻り値integer-array
- 新しいリストの順序での値
制約
1 ≤ L ≤ 5000。ここで、Lはnextとvaluesの長さです。-1000 ≤ values[i] ≤ 10001 ≤ k ≤ Lnext[i]は-1または0からL-1までのノードインデックスです。- ノード
0から始まり、リストは各ノードをちょうど1回ずつ訪問してから-1に到達します。循環はありません。
例
- 入力
- next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
- 出力
- [2, 1, 4, 3, 5]
- 説明
- リストは
1, 2, 3, 4, 5（ノード0, 2, 4, 1, 3）と読み取れます。ペア1, 2と3, 4は逆順になり、5は単独でk = 2より短いため、最後に残ります。
- 入力
- next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
- 出力
- [30, 20, 10, 60, 50, 40, 70, 80]
- 説明
- リストは
10, 20, ..., 80と読み取れます。グループ10, 20, 30と40, 50, 60は逆順になっています。70, 80はk = 3より短いため、順序はそのままです。
- 入力
- next = [2, -1, 1]values = [7, 9, 3]k = 3
- 出力
- [9, 3, 7]
- 説明
- 配列は
7, 9, 3と読み取れますが、リストは7, 3, 9と読み取れます。kが長さと等しい場合、リスト全体が1つのグループになり、逆順になります：9, 3, 7。
発展問題
1つのグループを逆順にして、リストの残りの部分に対して再帰する形で書けますか？それには追加でどのくらいのメモリを使いますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
リスト全体を反転するには、前のノードと現在のノードという2つのポインターを使ってたどりながら、通過するたびに各リンクを反転します。
k個のノードを進んだところでたどるのを止め、リストの残りの部分をつないだままにする必要がある場合、何が変わるでしょうか？グループを反転する前に、
k個のノードが存在するか確認するため、kステップ先まで進みます。存在しない場合は、残りには手を加えません。たどり着いたノードはグループの直後にあり、グループの先頭ノードは最終的にそのノードにつながる必要があります。すでに完了した部分の最後のノードを保持します。グループを反転した後、そのノードをグループの新しい先頭ノードに向けます（最初のグループでは、そのノードが新しい先頭になります）。グループの元の先頭ノードは、完了した部分の最後のノードになります。
解説
リスト全体を反転するには、リンクを一度たどって反転します。ここではk個のノードごとに反転を止め、反転した各グループを、その前の部分と後ろのノードにつなぎ直す必要があります。値を配列にコピーしてブロックごとに反転する方法と、追加メモリO(1)で各グループをその場でつなぎ直す方法があります。
値をコピーし、各ブロックを逆順にする
考え方
node = next[node] を使ってノード 0 からたどり、値をリストの順序で配列にコピーします。グループはインデックスのブロック 0 から k-1、k から 2k-1、以下同様となります。全体が収まる各ブロックを反転し、最後の短いブロックはそのままにします。これは O(L) 時間と O(L) の追加メモリを使い、リンクには一切触れません。
アルゴリズム
- ノード
0から-1までたどり、values[node]を配列に追加します。 start = 0, k, 2k, ...について、start + k ≤ Lの間、インデックスstartからstart+k-1までのブロックを反転します。- 最後に短いブロックが残る場合は、そのままにします。
- 配列を返します。
def reverseKGroup(next, values, k):
# Read the values in list order.
order = []
node = 0
while node != -1:
order.append(values[node])
node = next[node]
# Reverse every full block of k; a shorter last block stays as it is.
for start in range(0, len(order) - k + 1, k):
order[start:start + k] = order[start:start + k][::-1]
return orderリンクを付け替えて各グループをその場で反転する
考え方
リスト全体を逆順にするには、prevとnodeを使ってたどり、next[node] = prevと設定します。グループの場合も同じループをk回実行しますが、prevはグループの直後のノードであるafterから始めます。グループの先頭ノードは末尾になり、afterにつながるため、リストの残りの部分もつながったままです。
反転する前にk個のノードを数えます。先に-1に到達した場合、残りは短いグループなので、そのままにします。反転後、prevはグループの新しい先頭ノードです。前のグループの末尾ノードをそこにつなぐか、最初のグループならそれを先頭にします。グループの元の先頭ノードは、反転済み部分の末尾ノードになります。
各ノードには、数えるときと反転するときの2回アクセスします。時間計算量はO(L)で、必要なメモリは整数数個です（Rではリンクベクトルが最初の変更時にコピーされるためO(L)）。
アルゴリズム
head = 0、prevTail = -1、groupStart = 0で開始します。groupStartからafterまでkステップ進みます。先に-1に到達した場合は、手順5に進みます。prev = after、node = groupStartとして、k回繰り返します。next[node]を保存し、next[node] = prevを設定して、両方を進めます。prevTailが-1の場合は、head = prevを設定します。そうでない場合は、next[prevTail] = prevを設定します。prevTail = groupStart、groupStart = afterを設定し、手順2に進みます。headから値を収集します。
def reverseKGroup(next, values, k):
head = 0 # the list's head; changes after the first group
prev_tail = -1 # last node of the groups already reversed
group_start = 0
while True:
# Find the node right after this group, or stop if fewer than k remain.
after, count = group_start, 0
while after != -1 and count < k:
after = next[after]
count += 1
if count < k:
break
# Turn the group's k links around. Its first node ends up last
# and links to the node after the group.
prev, node = after, group_start
for _ in range(k):
following = next[node]
next[node] = prev
prev, node = node, following
# prev is the group's new first node: hang it after the previous group.
if prev_tail == -1:
head = prev
else:
next[prev_tail] = prev
prev_tail = group_start
group_start = after
# Walk the relinked list from its head.
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result
落とし穴と境界ケース
- 最後の短いグループを反転すること。反転する前に
k個のノードを数えましょう。リンクを反転すると、もう一度走査しない限り元に戻せません。 - 全体を反転するときのように、
prev = -1で反転を始めること。すると短い末尾が切り離され、最初の例では2, 1, 4, 3が返されます。 - 前のグループの最後のノードを、新しい先頭ノードにつながないこと。前のグループの最後のノードは古い先頭ノードを指したままなので、
k-1個のノードが失われます。 - ノード
0から答えを読み取ったり、valuesを左から右へ読み取ったりすること。k ≥ 2のグループを反転すると、ノード0は先頭ではなくなり、配列の順序はそもそもリストの順序ではありません。 - 配列が1から始まるLuaとRで、0からインデックスを付けること。ノードのインデックスは0ベースのままにし、
next[node + 1]を読み取りましょう。
よくある質問3
ノードを k 個ずつのグループで反転する場合の時間計算量と空間計算量は何ですか？
L 個のノードからなるリストに対して、実行時間は O(L) です。各ノードは一度数えられ、一度反転されます。インプレース版で使用する追加メモリは O(1) です。値を配列にコピーする場合は O(L) です。
最後のグループのノード数が k 未満の場合、どうなりますか？
元の順序を保ちます。各グループを反転する前にk個のノードを数えます。先にリストの末尾に達した場合は、残りをそのままにします。
なぜこの問題の解法ではダミーノードを使うのですか？
ノードオブジェクトでは、先頭の前にダミーノードを置くことで、最初のグループの前にもノードができ、1本の線ですべてのグループを完成済みの部分につなげられます。リンクの配列では、最初のグループが完了するまでprevTailが-1のままであることで、同じ役割を果たします。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def reverseKGroup(next, values, k):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
next = [2, 3, 4, -1, 1] values = [1, 4, 2, 5, 3] k = 2
期待される出力
[2, 1, 4, 3, 5]