Palindrome Linked List
同じ長さの2つの配列に格納された単方向連結リストが与えられます。ノード i は値 values[i] を保持し、ノード next[i] へのリンクを持ちます。-1 はリストの終端を示し、先頭ノードは 0 です。ノードはリストの順序どおりには格納されていないため、リンクをたどってください。
先頭から末尾まで読み取った値の並びが、末尾から先頭に向かって読み取った並びと同じ場合は true を、そうでない場合は false を返してください。
関数
- nextinteger-array
- 各ノードがリンクしているノードのインデックス。最後のノードの場合は -1
- valuesinteger-array
- 各ノードが保持する値
- 戻り値boolean
- リストをどちらの方向から読んでも同じ場合は true
制約
1 ≤ L ≤ 5000、ここでLはnextとvaluesの長さです。-100 ≤ values[i] ≤ 100- 各
next[i]は-1または0からL-1までのノードインデックスです。 - ノード
0から始まり、リストは各ノードをちょうど1回ずつ訪れ、その後-1に到達します。サイクルはありません。
例
- 入力
- next = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
- 出力
- true
- 説明
- リンクはノード
0, 4, 1, 3, 2を訪れるため、リストは3, 1, 4, 1, 3となります。2つの3は一致し、2つの1も一致します。中央の4には照合する相手がありません。
- 入力
- next = [2, -1, 3, 1]values = [4, 4, 9, 9]
- 出力
- true
- 説明
- リストはノード
0, 2, 3, 1を訪れ、4, 9, 9, 4を読み取ります。どちらの方向でも同じです。
- 入力
- next = [2, -1, 1]values = [1, 2, 1]
- 出力
- false
- 説明
- 配列
valuesは[1, 2, 1]ですが、リストはノード0, 2, 1をたどり、1, 1, 2を読み取ります。逆順にすると2, 1, 1なので、答えはfalseです。
発展問題
追加メモリ O(1) で、O(L) 時間で実行できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
回文のチェックでは、最初の値を最後の値と、2番目の値を最後から2番目の値と比較し、以下同様に行います。単方向リンクリストでは前方にしか進めません。末尾に到達できるようにするには、どうすればよいでしょうか？
値をリストの順序で配列にコピーすれば動作しますが、メモリを
O(L)消費します。コピーしない場合は、後半を逆順にたどる必要があります。リンクを変更すれば、それが可能になります。2つのポインターで中央を見つけます。
fastはslowが1つ進むたびに2つリンクを進みます。fastがそれ以上進めなくなったとき、slowは前半の終わりにあります。slowの後ろのリンクを反転させ、その後、先頭ノードと元の最後のノードから同時に進み、比較します。
解説
回文の判定では、各値を反対側の端にある対応する値と照合します。単方向連結リストは前方にしか進めないため、後半部分を逆順に読み取るのが難しい点です。配列にコピーすると O(L) のメモリを使います。ここで、L はノード数です。後半部分のリンクを反転すれば、O(1) で済みます。
値を配列にコピーする
考え方
ここでのポインターはノードのインデックスで、次へ進むには node = next[node] とします。リストを一度たどり、各値を配列にコピーします。この配列は両端から読み取れます。先頭と末尾の値を比較し、両方のインデックスを中央に向かって進め、不一致があれば false を返します。長さが奇数の場合、中央の値はそれ自身が対応する値です。
すべての値を読み取る必要があるため、時間計算量は O(L) が最善です。追加で L 個の整数が必要です。
アルゴリズム
- ノード
0から-1まで移動し、各values[node]を配列に追加します。 i = 0に設定し、jを最後のインデックスに設定します。i < jの間、2つの値が異なる場合はfalseを返し、そうでなければiを増やし、jを減らします。trueを返します。
def isPalindrome(next, values):
# Write the values out in list order.
seq = []
node = 0
while node != -1:
seq.append(values[node])
node = next[node]
# Compare from both ends toward the middle.
i = 0
j = len(seq) - 1
while i < j:
if seq[i] != seq[j]:
return False
i += 1
j -= 1
return True後半部分をその場で反転する
考え方
後半部分をコピーするのではなく、リンクを逆順にします。古い最後のノードからたどると、中央に向かって進めます。中央を見つけるには、fast が2つ先までリンクを持つ間、slow が1つ進むごとに fast を2つ進めます。slow は前半の最後のノードで停止します。L が奇数の場合は中央のノードです。最初の例では、slow は 0 → 4 → 1 と進み、fast は 0 → 1 → 2 と進むため、slow は 4 で停止します。
slow の後ろにあるノードを逆順にしてから、先頭から left を、逆順にした半分から right を同時にたどります。3 と 3、続いて 1 と 1 を比較します。逆順にした半分が前半より長くなることはないため、right が終わった時点で停止すれば、比較すべき組だけを正確に比較できます。各段階でたどるノードは最大でも L 個で、格納するのは少数の整数だけです。R では、next_ を変更するとベクトルが1回コピーされるため、R のメモリ使用量は O(L) です。
アルゴリズム
slow = fast = 0に設定します。next[fast]とnext[next[fast]]がどちらも-1でない間、slowを1リンク、fastを2リンク進めます。next[slow]から始まるリストを逆順にします。各ノードについて、リンクを保存し、そのノードのリンク先をprevに設定してから、prevとノードを前に進めます。left = 0、right = prev（逆順にした半分の先頭）に設定します。right != -1の間、不一致があればfalseを返し、そうでなければ両方のポインターを1リンク進めます。trueを返します。
def isPalindrome(next, values):
# Find the middle: fast moves two links for every one link slow moves.
slow = 0
fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
# slow is the last node of the first half (the middle node when the length is odd).
# Reverse the links of the second half.
prev = -1
node = next[slow]
while node != -1:
after = next[node]
next[node] = prev
prev = node
node = after
# prev is the old last node, now the head of the reversed half.
left = 0
right = prev
while right != -1:
if values[left] != values[right]:
return False
left = next[left]
right = next[right]
return True
落とし穴と境界ケース
- リストではなく配列を確認している。3つ目の例では
valuesは[1, 2, 1]だが、リストの値は1, 1, 2となっている。 next[fast] != -1だけをテストしている。その場合、fastが-1まで進んでnext[-1]を読み取る可能性がある。これはほとんどの言語では範囲外となり、PythonとRubyではエラーにならず最後の要素を指す。rightではなくleftが終わるまで比較している。中央のノードは引き続き元の後半部分につながっているため、先頭からたどる経路のほうが長い。- 反転中に保存する前に
next[node]を上書きしており、リストの残りが失われる。 - 配列のインデックスが1から始まるLuaとRで、0ベースのノードIDに対して
next[node]を読み取っている。next[node + 1]を読み取る。
よくある質問3
回文連結リストの判定の時間計算量はどれくらいですか？
どの方法も、各値を比較する必要があるため、L 個のノードからなるリストに対して O(L) です。値を配列またはスタックにコピーすると、追加で O(L) のメモリを使用します。後半をその場で反転すると、O(1) です。
速いポインターと遅いポインターは、どのように連結リストの中央を見つけるのでしょうか？
どちらも先頭から始まり、速いポインターは遅いポインターの1歩につき2歩進みます。速いポインターが末尾に到達したとき、リスト全体を進んでおり、遅いポインターはその半分を進んでいます。
リストの半分を逆順にすると、入力は破壊されますか？
はい、後半部分のリンクが変更されます。また、ほとんどの言語では、その配列は呼び出し元自身のものです。リストが引き続き必要なら、早期に戻らずに比較を最後まで行い、その後、後半部分をもう一度反転させます。中央のノードは引き続き後半部分の先頭ノードにつながっているため、リストは再び全体がつながった状態になり、追加メモリは O(1) です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def isPalindrome(next, values):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
next = [4, 3, -1, 2, 1] values = [3, 4, 3, 1, 1]
期待される出力
true