プロンプトと適用可能な文脈
非巡回な単方向連結リストの先頭が与えられ、各ノードには val、next、random が含まれます。random ポインタは null であるか、自身を含むリストの next チェーンを通じて到達可能な任意のノードを参照します。元の各ノードに対して正確に1つの新しいノードを持つディープコピーを返してください。元のノード x がいずれかのフィールドを通じて元のノード y を指している場合、x のコピーはそのフィールドを通じて y のコピーを指す必要があります。
ノードの値は一意ではないため、値によってノードを識別することはできません。next チェーンは有限ですが、random エッジは後方、前方を指す場合やサイクルを形成する場合があります。返されるリストは入力とノードを共有してはならず、関数が戻る際に入力は元の構造を維持していなければなりません。
これはデータ構造とオブジェクトの同一性（identity）に関する問題です。基本となる解法は、元の各オブジェクトからそのコピーへのマップを使用します。発展的な質問として定数補助空間が求められる場合があります。そのバージョンでは、一時的にコピーを元のノードの間にインターリーブ（挿入）し、後で入力を復元します。出力ノードは補助空間にはカウントされませんが、全体として O(n) のメモリを消費します。
面接官が評価するポイント
第1の評価ポイントは、候補者がディープコピーを構造的に定義しているかどうかです。値が等しいだけでは不十分です。元のノードから新しいノードへの1対1のマッピング f が存在し、両方の関係が保持されている必要があります。すなわち、x.next のコピーが f(x).next であり、x.random のコピーが f(x).random であることです。
第2の評価ポイントは、参照先がコピーされる前の参照の扱いです。1パスの値コピーでは、前方を指す random エッジを安全に接続できません。直接的な解決策は、メモリ割り当てとポインタの接続を分離することです。まずすべての宛先ノードを作成し、次に同一性マップを通じてポインタを接続します。
第3の評価ポイントは、空間最適化を単に暗記して暗唱するのではなく論理的に導出できるかです。各コピーを元のノードの直後に配置すると、元の任意のノード r のコピーは正確に r.next になります。この局所的な不変条件により、ランダムポインタの割り当て時にマップが不要になります。
最後に、面接官はミューテーション（変更）に対する規律を確認します。インターリーブ手法は、元のすべての next ポインタを復元し、有効なコピーチェーンを抽出し、入力を一時的に変更することが受け入れられないケースを説明して初めて完成します。
回答前に確認すべき質問
randomはリストの外を指すことがありますか？ この問題文では指さないとされています。外部ノードもクローンに含める場合、スコープは一般的な到達可能グラフのコピーになります。含めない場合、出力の仕様としてそれらの参照を保持、クリア、または拒絶するかを規定する必要があります。nextチェーンにサイクルが含まれることはありますか？ いいえ。もし含まれる場合、nextのみをたどるループは訪問済みセットなしには終了しなくなり、グラフのクローンとして扱う方が適切になります。- アルゴリズムは入力を一時的に変更してもよいですか？ マップを用いた解法は変更しません。インターリーブ解法は変更を伴うため、関数が排他的な変更アクセス権を持ち、戻る前にリストを復元する場合にのみ適しています。
- 何が追加空間としてカウントされますか？ コピーされたノードは要求されている出力です。マップは
O(n)の補助空間を消費します。インターリーブは、O(n)の出力に加えてO(1)の補助ポインタを使用します。 - 値は一意ですか？ いいえ。値をキーとするマップは異なるノードを統合してしまい参照を破壊します。キーはノードの同一性でなければなりません。
- 空の入力に対しては何を返すべきですか？
nullを返します。
30秒の回答フレームワーク
「まず、元ノードからコピーへの同一性マップを用いて解きます。1回目のパスでコピーノードをすべて割り当て、2回目のパスで対応する元の参照先をルックアップしてコピーされた next および random ポインタを設定します。これは時間計算量 O(n)、補助空間 O(n) です。面接官が定数補助空間を求め、一時的な変更が許可されている場合は、各コピーを元のノードの直後に挿入できます。これにより、元のランダム参照先のコピーはその次のノードになります。3回目のパスで入力を復元しながらチェーンを分離します。どちらの手法も線形時間であり、インターリーブ版は必要な出力を除いて O(1) の補助空間を使用します。」
ステップバイステップの詳細な回答
シャローコピー（浅いコピー）は元の参照を再利用するため不適切です。値のみのコピーも失敗します。2つの異なるノードが同じ値を持つ可能性があり、random が走査でまだ出現していないノードを指す場合があるためです。ランダムエッジがサイクルを形成する可能性があるため、random を再帰的にたどることは近道にはなりません。
最も安全なベースラインは、明示的に全単射を作成することです。1回目のパスで元のノードごとに1つの新しいオブジェクトを割り当てます。2回目のパスで、そのマップを介して両方の出力エッジを変換します。ルックアップに null -> null を含めることも可能ですが、面接では明示的な null チェックを行う方が通常は明確です。
class RandomListNode {
val: number
next: RandomListNode | null
random: RandomListNode | null
constructor(
val: number,
next: RandomListNode | null = null,
random: RandomListNode | null = null,
) {
this.val = val
this.next = next
this.random = random
}
}
function copyWithMap(head: RandomListNode | null): RandomListNode | null {
if (head === null) return null
const copies = new Map<RandomListNode, RandomListNode>()
let current: RandomListNode | null = head
while (current !== null) {
copies.set(current, new RandomListNode(current.val))
current = current.next
}
current = head
while (current !== null) {
const copy = copies.get(current)!
copy.next = current.next === null ? null : copies.get(current.next)!
copy.random = current.random === null ? null : copies.get(current.random)!
current = current.next
}
return copies.get(head)!
}1回目のパスの後の不変条件は単純です。next を通じて訪問されたすべての元のノードはマップ内に正確に1つの個別エントリを持ち、コピーされたポインタが未割り当てのノードを指す必要はありません。2回目のパスでは、x から y へのエッジを f(x) から f(y) へのエッジに変換することでグラフ構造が保持されます。この手法は2回の線形パスを行うため、時間は O(n)、補助空間は O(n) です。
マップを排除するには、同じ対応関係をリストのトポロジ内に一時的に保持します。このチェーンを：
A -> B -> C -> null次のインターリーブされたチェーンに変換します：
A -> A' -> B -> B' -> C -> C' -> nullこれで A' は A.next となり、A.random が C を指している場合、A'.random の正しい参照先は A.random.next、すなわち C' になります。これはオブジェクトの位置に依存し、値には依存しないため、前方エッジ、後方エッジ、自己参照、重複した参照先でも正しく機能します。
function copyByInterleaving(head: RandomListNode | null): RandomListNode | null {
if (head === null) return null
let current: RandomListNode | null = head
while (current !== null) {
const copy: RandomListNode = new RandomListNode(current.val, current.next)
current.next = copy
current = copy.next
}
current = head
while (current !== null) {
const copy: RandomListNode = current.next!
copy.random = current.random === null ? null : current.random.next
current = copy.next
}
const copiedHead = head.next
current = head
while (current !== null) {
const copy: RandomListNode = current.next!
const nextOriginal: RandomListNode | null = copy.next
current.next = nextOriginal
copy.next = nextOriginal === null ? null : nextOriginal.next
current = nextOriginal
}
return copiedHead
}正当性は3つのパスの不変条件から導かれます。パス1の後、各元のノードの直後にその一意のコピーが続きます。パス2の間、コピーされたすべてのランダムエッジは、元の参照先の直後にあるコピーを指します。パス3の間、各反復で1つの元のエッジを復元し、1つのコピーされたエッジを次のコピーノードに接続します。ループが終了すると、元のチェーンが復元され、コピーされた先頭から到達可能なすべてのポインタはコピーされたノードのみを指すようになります。
インターリーブ手法は3回の線形パスを実行するため、時間は O(n) のままです。固定数の作業用ポインタのみを保持するため、必要な n 個の新しいノードを除いて、補助空間は O(1) です。ただし、これが本番環境で自動的に優れた選択肢になるわけではありません。最初の2回のパスの間、他のスレッド等からは入力が壊れているように見え、分離処理の前に例外が発生するとリストがインターリーブされたままになる可能性があります。マップによる解法は監査が容易であり、不変または共有された入力をサポートします。
構造、同一性、復元を個別にテストしてください。空のリスト、random = null を持つ1つのノード、random が自身を指す1つのノード、重複する値、2つのノードのランダムポインタが交差しているケース、前方および後方のランダムエッジ、多数のノードが同じ宛先を指すケースをカバーします。クローン作成後、コピーされた値を変更して元の値が変化しないことを確認します。再度元のリストを走査して next チェーンが復元されたことを確認し、コピーされた next または random ポインタのいずれも元のノードセットに属していないことをアサートします。
質の高い模範解答
「重要なのは、値だけでなくノードの同一性を保持することです。値は重複する可能性があり、ランダムエッジは前方を指すことやサイクルを形成することがあるため、値をキーにしたり、訪問状態を持たずにランダムポインタを再帰的にたどったりすることは避けます。
私のベースラインは同一性マップを用いた2パスの解法です。1回目のパスで非巡回な next チェーンを走査し、元のノードごとに1つのコピーを割り当てます。2回目のパスでマップを介して両方のポインタを変換します。これにより1対1の対応が直接確立され、線形時間および線形補助空間で動作します。入力が不変、共有されている場合、または最もシンプルで監査しやすい実装が重要な場合には、このバージョンを選択します。
定数補助空間が厳格な要件であり一時的な変更が許可されている場合は、各コピーを元のノードの直後に挿入します。これによりマッピングが暗黙的になります。すなわち、元の参照先のコピーは target.next です。その後、コピーされたすべてのランダムポインタを割り当て、交互になっているチェーンを分離します。分離パスでは両方のチェーンを更新する必要があるため、元のチェーンは完全に復元され、コピーには元のリストへの参照が一切残りません。
ウィービング（挿入）、ランダムポインタの割り当て、分離の後の3つの不変条件を証明し、自己参照 random、重複値、交差するランダムエッジ、空の入力、コピー後の独立性をテストします。どちらのバージョンも時間計算量は O(n) です。2つ目は補助空間が O(1) ですが、依然として O(n) の出力を割り当て、並行リーダーに対して安全ではありません。」
よくある間違い
- ノードの値をマップのキーにする -> 重複する値によって別々の同一性が統合されてしまう -> 元のノードオブジェクトをキーにする。
randomを直接コピーする -> 出力が依然として入力を指してしまう -> null 以外のすべての宛先をコピーされたノードに変換する。- 1回の単純な前方パスで割り当てと接続を行う -> 前方のランダム参照先がまだ存在しない可能性がある -> すべてのノードを先に割り当てるか、完全な同一性マップを介して不足しているコピーを作成する。
- 訪問状態なしでランダムポインタを再帰的にたどる -> ランダムのサイクルによって無限再帰やノードの重複が発生する -> この問題の制約では有限な next チェーンを使用するか、一般的なグラフでは visited マップを使用する。
- インターリーブ手法を注釈なしで空間
O(1)と呼ぶ -> 返されるリストには依然としてn個の新しいノードが含まれる -> 必要な出力を除いて補助空間O(1)と表現する。 - null チェックなしで
copy.random = current.random.nextを割り当てる -> null のランダムポインタでクラッシュする -> null を明示的に保持する。 - コピーされたチェーンのみを切り離す -> 元のノードがコピーを経由してリンクされたままになる -> 同じ分離パス内で元のチェーンを復元し、コピーされたチェーンを構築する。
- 共有入力に対してインターリーブを使用する -> 並行リーダーが挿入されたコピーを読み取ってしまう -> 排他的な一時的変更が保証されていない限りマップ解法を使用する。
- 値のみをテストする -> シャローコピーでも値の比較を通過してしまう -> 異なる同一性、変換されたエッジ、元のリストの復元、変更に対する独立性をアサートする。
フォローアップ質問と回答
フォローアップ1：入力が一時的にも一切変更できない場合はどうしますか？
同一性マップによる解法を使用します。これにより、実行全体を通じて元のデータを変更することなく、時間 O(n)、補助空間 O(n) が得られます。走査インデックスによって配列にコピーする方法も O(n) の空間を消費し、入力が安定したインデックスをすでに公開していない限り同一性からインデックスへのマッピングが依然として必要になります。インターリーブ最適化は、後でリストを復元したとしても、より厳格なイミュータビリティ（不変性）の規約に違反します。
フォローアップ2：random が next チェーンの外部のノードを指す可能性がある場合はどうしますか？
まずクローンの所有権スコープを定義します。外部ノードもコピーする必要がある場合、入力は next と random を出次数エッジとするグラフになります。同一性マップを用いた DFS または BFS を使用し、到達可能なすべてのノードを1回ずつクローンします。外部ノードが意図的に共有されている場合は、保持された外部参照を許可する仕様である必要があります。インターリーブ手法では、任意の外部ターゲットに対するコピーの検出や配置ができません。
フォローアップ3：next ポインタがサイクルを形成できる場合はどうしますか？
単純な while current !== null による走査は終了しなくなります。両方のフィールドをグラフのエッジとして扱い、訪問済みの同一性マップを保持します。ノードが最初に発見されたときにそのコピーを作成し、未訪問の隣接ノードをキューに追加します。このモデルではノードごとに最大2つの出次数エッジが存在し、到達可能グラフ全体に対する時間と空間は O(V + E) になります。
フォローアップ4：コピーが真にディープコピーであることをどのように検証しますか？
両方の next チェーンを走査しながら、テスト内でのみ元の同一性からコピーされた同一性へのマップを構築します。長さと値が等しいこと、ノードの同一性が異なること、および各エッジについてコピーされた参照先がマップされた元の参照先と等しいことをアサートします。また、出力ポインタのいずれも元のノードセットに含まれていないことをアサートします。最後に、コピー側の値やポインタを変更して元のデータが不変であることを確認します。インターリーブの場合は、呼び出し前と呼び出し後の元のポインタ同一性を比較します。
フォローアップ5：どの解法を本番環境にデプロイしますか？
不変条件が明示的であり、一時的に変更された入力を外部に公開することが一切ないため、デフォルトでは2パスのマップ版を選択します。インターリーブは、補助メモリが実測上の制約となっており、呼び出し全体を通じてリストが排他的に所有され、エラー処理によって復元が保証できる場合にのみ選択します。漸近的な空間計算量の改善は、並行性、例外安全性、保守性のコストを打ち消すものではありません。