Middle of the Linked List
同じ長さの2つの配列に格納された単方向連結リストが与えられます。ノード i は値 values[i] を持ち、ノード next[i] へのリンクを持ちます。-1 はリストの終端を表し、先頭ノードは 0 です。ノードはリストの順序どおりには格納されていないため、リンクをたどってください。
中央のノードの値を返してください。リストのノード数が偶数の場合、中央のノードは2つあります。そのうち後方のノードの値を返してください。
関数
- valuesinteger-array
- 各ノードが保持する値
- nextinteger-array
- 各ノードがリンクしているノードのインデックス。最後のノードの場合は -1
- 戻り値integer
- 中央ノードの値。長さが偶数の場合は、中央にある2つのノードのうち2番目の値
制約
1 ≤ n ≤ 5000。ここで、nはvaluesとnextの長さです。-104 ≤ values[i] ≤ 104- 各
next[i]は-1、または0からn-1までのノードインデックスです。 - ノード
0から始まり、リストは各ノードをちょうど1回ずつ訪れてから、-1に到達します。サイクルはありません。
例
- 入力
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- 出力
- 5
- 説明
- ノード
0からリンクをたどると、ノード0, 3, 4, 2, 1となるため、リストは4, 7, 5, 2, 9の順になります。5つのうち3番目はノード4で、その値は5です。配列自体の中央の要素values[2] = 2は別のノードです。
- 入力
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- 出力
- 40
- 説明
- ここではノードが順番に格納されています。ノードが6つある場合、中央のノードは2つあり、
30と40のうち、2番目のものが選ばれます。
- 入力
- values = [8]next = [-1]
- 出力
- 8
- 説明
- ノードが1つのリストでは、そのノード自体が中央です。
提出時に隠しテスト+13件
発展問題
リストを1回走査するだけで、先頭から3分の1の位置にあるノードを返せますか？それぞれのポインターをどのくらいの速さで進め、どこで止めますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
リストの末尾にたどり着くまで、その長さはわかりません。2人の走者が先頭から出発し、片方がもう片方の2倍の速さで進んだとしたらどうでしょうか？
速いほうの歩行者が末尾に到達したとき、遅いほうは距離の半分を進んでいるため、中央のノードにいます。残る唯一のポイントは、長さが偶数の場合に2つ目の中央に到達するよう、いつ停止するかです。
slowとfastをノード0から開始します。fastが-1ではなく、next[fast]も-1ではない間、slowを1つ、fastを2つリンク先へ進めます。その後、values[slow]を返します。
解説
配列では、中央はインデックス n / 2 にあります。連結リストにはインデックスがありません。末尾までたどって初めて長さがわかりますが、その頃には中央を通り過ぎています。リストを配列にコピーするか、まず数えてからもう一度たどる方法もあります。すっきりした解決策は、2つのポインターを異なる速度でリスト上に進めることです。速いポインターが最後まで進んだとき、遅いポインターはちょうど中央にいます。
値を配列にコピーする
考え方
この問題では、ポインターはノードのインデックスです。次のノードへ進むにはnode = next[node]とし、-1に到達すると末尾を越えたことになります。最初の例では、ノード0からたどると0 → 3 → 4 → 2 → 1 → -1となります。
リストの難点は、位置を指定してジャンプできないことです。そこで、位置を指定できる形に変えます。リストを一度たどりながら、通過するたびに各値を新しい配列に追加します。この配列にはリストの順序どおりに値が格納されます。最初の例では[4, 7, 5, 2, 9]となり、その中央は整数除算でインデックスlength / 2にあります。
このインデックスを使えば、要素数が偶数の場合に2つ目の中央の値が得られます。値が6個ならインデックス3、つまり4番目の値となり、2つ目の例では40です。リストをたどる処理には時間がO(n)かかり、コピーには追加メモリがO(n)必要ですが、次の2つの方法ではこれらを避けられます。
アルゴリズム
- 空の配列と
node = 0から始めます。 nodeが-1でない間、values[node]を追加し、next[node]に移動します。- インデックス
length / 2の要素を切り捨てて返します。
def middleNode(values, next):
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
return in_order[len(in_order) // 2]数えてから、半分まで歩く
考え方
リスト全体をコピーする必要はなく、長さだけで十分です。リストを一度たどってノード数を数えます。次に、先頭からもう一度たどり、length / 2歩進みます（小数点以下は切り捨てます）。止まったノードが中央です。
歩数がこれだけでよい理由は、k歩進むと、先頭を位置0として数えたとき、位置kのノードにたどり着くからです。5個のリストの中央は位置2で、6個のリストの2つ目の中央は位置3です。どちらもlength / 2です。最初の例では、5個と数え、2歩進んで0 → 3 → 4となり、values[4] = 5を読み取ります。
これでメモリ使用量はO(1)です。代わりにリストの半分をもう一度たどる必要がありますが、合計の移動回数は1.5nで、依然としてO(n)です。
アルゴリズム
- ノード
0から-1まで進み、ノードの数を数えます。 - ノード
0に戻ります。 node = next[node]をちょうどcount / 2回、切り捨てて実行します。values[node]を返します。
def middleNode(values, next):
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
node = 0
for _ in range(length // 2):
node = next[node]
return values[node]高速ポインターと低速ポインター
考え方
2つのポインターを先頭に置きます。各反復で、slowはノードを1つ進み、fastは2つ進みます。k回反復すると、slowは位置kに、fastは位置2kにいるため、slowが進んだ距離は常にfastの距離の半分です。fastが末尾に到達すると、slowは中央にいます。長さを調べる必要はありません。
停止条件によって、どちらの中央のノードを得るかが決まります。fastが有効なノードで、かつその次のノードが存在する間、処理を続けます。つまり、fast != -1かつnext[fast] != -1です。長さが奇数の場合、fastは最後のノードで停止します。長さが偶数の場合、fastは末尾を越えて-1に進み、その結果slowはもう1つ先、つまり2つある中央のうち後ろのノードに進みます。2つ目の例では、slowは0, 1, 2, 3と進み、fastは0, 2, 4, -1と進みます。また、values[3]は40です。
1つ目の例では、slowはノード0, 3, 4を訪れ、fastは0, 4, 1を訪れます。ノード1が最後のノードなので、ループはslowがノード4にいる状態で停止し、答えは5です。fastは約n回、slowはn / 2回進み、1回の走査で済み、メモリ使用量は整数2つ分です。
アルゴリズム
slow = 0とfast = 0を設定します。fast != -1かつnext[fast] != -1の間、slow = next[slow]とfast = next[next[fast]]を設定します。values[slow]を返します。
def middleNode(values, next):
slow = fast = 0
# Stop when fast is on the last node or has stepped past it.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
return values[slow]
落とし穴と境界ケース
ループは短いため、間違いは開始位置、終了位置、戻り値にあります。
values[n / 2]を返す。ノードはリスト順に格納されていないため、配列の中央の要素は通常、別のノードです。最初の例では、5ではなく2が返されます。- 長さが偶数のとき、最初の中央のノードを取得してしまう。
next[fast]とnext[next[fast]]がどちらも実在する間ループする場合、1ラウンド早く停止し、2つ目の例では40ではなく30を返します。 fast != -1より前にnext[fast]を確認する。長さが偶数の場合、fastは-1になり、多くの言語ではnext[-1]を読み取るとクラッシュします。Pythonでは代わりに最後の要素をエラーなく読み取ってしまい、さらに厄介です。- 数え上げ方式で
count / 2 - 1歩進む、または切り上げる。先頭を位置0として数え、切り捨てたcount / 2歩だけ進みます。 - 値ではなくノードのインデックスを返す。
- 配列のインデックスが1から始まるLuaとRで、オフセットを忘れる。ノードのインデックスは0始まりのままにして、
next[node + 1]を読み取ります。RubyとRではnextという語が予約されているため、スターターコードではパラメーター名をnext_にしています。
よくある質問4
高速ポインターと低速ポインターを使うと、なぜ連結リストの中央を見つけられるのでしょうか？
どちらも先頭から始まり、各ラウンドで高速ポインターは2つのノードを進み、低速ポインターは1つ進みます。kラウンド後、高速ポインターは位置2kに、低速ポインターはkにあり、ちょうど半分の距離です。したがって、高速ポインターがリストの末尾に到達したとき、低速ポインターはその中央にあります。
連結リストの中央を見つける時間計算量と空間計算量はどれくらいですか？
中央の要素を見つけるには、リストの半分ほど、またはそれ以上をたどる必要があるため、3つの方法はいずれも時間計算量は O(n) です。値をコピーすると、追加のメモリを O(n) 使用します。最初に数える方法と、高速ポインターと低速ポインターを使う方法はいずれも O(1) で、ポインターを使う方法では1回たどるだけで済みます。
2番目ではなく、最初の中央ノードを返すにはどうすればよいですか？
高速ポインターが1周早く停止するように停止条件を変更します。next[fast] != -1かつnext[next[fast]] != -1の間、ループします。ノードが6個の場合、低速ポインターは3ではなく位置2で停止します。カウント方式では、count / 2ではなく(count - 1) / 2ステップ進みます。
高速ポインターと低速ポインターの手法は、ほかにどこで使われていますか？
同じ2つの速度を使って、連結リスト内のサイクルも検出できます。ループ内では速いポインターが遅いポインターに追いつき、2つが出会います。また、サイクルの開始位置を見つけたり、マージソートやリストが前後どちらから読んでも同じかどうかを確認するために、リストを半分に分割したりできます。
Python
def middleNode(values, next):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
期待値
5