プロンプトと適用可能な文脈
単方向連結リストの先頭 head と正の整数 k が与えられたとき、連続する k 個のノードからなる各完全なグループを in-place で反転してください。末尾に残ったノードが k 個未満の場合は、元の順序を 維持します。value フィールドの値を交換するのではなく、ノードのポインタを繋ぎ替えてください。
例えば、1 → 2 → 3 → 4 → 5 は k = 2 のとき 2 → 1 → 4 → 3 → 5 となり、 k = 3 のとき 3 → 2 → 1 → 4 → 5 となります。1 ≤ k ≤ n ≤ 5000 であり、入力は非循環（acyclic）、目標は O(n) の時間計算量と O(1) の追加空間計算量であると仮定します。
この問題は、アルゴリズム、バックエンド、インフラストラクチャ、および一般的なソフトウェアエンジニアリング職の コーディング面接に適しています。難しいのは単純なリストの反転そのものではありません。変更を加える前に完全なグループが存在することを証明し、 次のグループへの進入点を保持し、両側の境界を正しく再接続し、ノードの欠落やサイクルの発生がないことを示す点にあります。
面接官が評価するポイント
最初の評価シグナルは、候補者が境界の特定、セグメントの反転、および再接続を明確に分離して扱えているかです。 k 個のノードが残っていることを確認する前に反転を開始すると、不完全な末尾グループを追加のメモリなしで 元の状態に戻すことが困難になります。優れた解法では、ポインタを変更する前に読み取り専用の先読み（lookahead）を実行します。
2 つ目のシグナルは、ポインタの責任関係の明確さです。groupPrev は現在のグループの直前に位置し、kth は完全なグループの 末尾ノード、groupNext は後続セグメントへの進入点であり、反転前のグループ先頭は反転後の新しい末尾になります。 各反復の終了時に、完了したプレフィックスへの到達可能性が維持され、groupPrev.next が最初の未処理ノードでなければなりません。
3 つ目のシグナルは、コードの暗記ではなくループ不変条件（invariant）の理解です。prev を groupNext で初期化することで、 元のグループ先頭が新しい末尾になった際にサフィックスを指すようになります。反転が完了した後は、直前のプレフィックスを kth に接続するだけで済み、グループとサフィックスの接続はすでに正しい状態になっています。
4 つ目のシグナルは、計算量の規律です。各ノードは、完全グループの先読みで最大 1 回、反転で最大 1 回訪問されるため、 合計は O(n) となり、固定数の参照を使用することで追加空間計算量は O(1) となります。再帰バージョンも 時間計算量は同じですが、グループ数に比例したコールスタック空間を消費します。
回答前に確認すべき質問
k個未満の最後のグループはどう扱いますか？ ここでは変更せずにそのまま残します。バリアントによっては反転させるものもあり、
その場合は結果が異なります。
- ノードの値を交換してもよいですか？ いいえ。ノードには同一性（identity）、外部参照、または値以外のフィールドが含まれる場合があるため、
値の交換はノードの反転とはみなされません。
kの取り得る値の範囲は？ プロンプトでは1 ≤ k ≤ nが保証されています。再利用可能な関数を作成する場合は、
非整数や 1 未満の値を拒絶するように設計できます。
- 入力にサイクルが含まれる可能性はありますか？ このプロンプトではサイクルはないとされています。サイクルが存在し得る場合、
それを拒否するか変換するかを契約として定義する必要があります。そうしないと先読みが終了しない可能性があります。
- アルゴリズムは in-place である必要がありますか？ はい。
O(k)の空間が許可されていればスタックを使う方が簡単ですが、
今回の制約を満たせません。
- ノードオブジェクト自体を再利用する必要がありますか？ はい。単に値をコピーして新しいリストを作成することは要件違反です。
30秒の回答フレームワーク
「head の前にダミーノードを配置し、現在のグループの直前に groupPrev を維持します。各反復において、 groupPrev から k ステップ進めて kth を探索します。見つからない場合は、末尾が変更されていないため 直ちにリターンします。groupNext = kth.next を保存した後、prev を groupNext で初期化し、現在のグループのポインタを 1 つずつ反転します。これにより、元のグループ先頭が新しい末尾となり、すでに groupNext を指すようになります。 groupPrev.next を kth に接続し、groupPrev を元のグループ先頭に移動します。各ノードは先読みで 1 回、反転で 1 回 訪問されるため、時間計算量は O(n)、追加空間計算量は O(1) となります。」
ステップバイステップの詳細解説
まずダミーノードを用意します。最初のグループが反転されるとリストの先頭が変化します。ダミーノードを使用することで、 プレフィックスを新しいグループ先頭に接続する処理が、最初のグループでもそれ以降のグループでも同一になり、特別な先頭処理を回避できます。
各反復では、最初に完全グループの先読みを行います。groupPrev から正確に k 回進めて kth を取得します。 ステップ途中で null に到達した場合は、残りのノードが k 個未満であるため、dummy.next を返します。先読み処理では 一切のポインタ書き込みを行っていないため、不完全な末尾グループは自動的に変更されないまま保たれます。
実装は以下の通りです：
class ListNode {
constructor(value, next = null) {
this.value = value
this.next = next
}
}
function reverseKGroup(head, k) {
if (!Number.isInteger(k) || k < 1) {
throw new RangeError('k must be a positive integer')
}
const dummy = new ListNode(0, head)
let groupPrev = dummy
while (true) {
let kth = groupPrev
for (let step = 0; step < k; step += 1) {
kth = kth.next
if (kth === null) {
return dummy.next
}
}
const groupNext = kth.next
let prev = groupNext
let current = groupPrev.next
while (current !== groupNext) {
const nextNode = current.next
current.next = prev
prev = current
current = nextNode
}
const oldGroupHead = groupPrev.next
groupPrev.next = kth
groupPrev = oldGroupHead
}
}1 → 2 → 3 → 4 → 5 において k = 3 の場合のトレース。先読みで kth = 3 が見つかり、groupNext = 4 が保存されます。 prev = 4 を設定し、1.next = 4、2.next = 1、3.next = 2 の順に書き換えます。ノード 3 がグループの新しい先頭になり、 ノード 1 は新しい末尾となって、すでにノード 4 に接続されています。ダミーノードを 3 に接続し、groupPrev を ノード 1 へ移動します。次の先読みでは 3 つのノードを見つけることができないため、4 → 5 に触れることなくリターンします。
ループ不変条件には 3 つの要素があります。ループ開始時、groupPrev までのプレフィックスは完全なグループごとに正しく変換されており、 groupPrev.next は最初の未処理ノードであり、未処理ノードはすべて入力順序のまま到達可能です。先読みが失敗した場合は書き込みが行われないため、 不完全な末尾が保持されることが不変条件から直接証明されます。先読みが成功すると反転対象が正確に k 個のノードに限定され、 groupNext がサフィックスへの進入点を保持します。再接続後、完了したプレフィックスは 1 グループ分拡大し、不変条件が回復します。成功した 各反復は k 個の新しいノードを消費するため、アルゴリズムは必ず終了します。
先読みと反転は、全反復を通じてもノードごとに最大 1 回ずつしかアクセスしません。したがって、全体の作業量は最大でも 約 2n 回のノード訪問となり、O(nk) ではなく O(n) となります。ダミーノードとポインタ数は入力サイズに依存しないため、 補助空間計算量は O(1) です。
追加のメモリが許可される場合、1 グループをスタックに push してから pop するアプローチは記述が容易ですが、O(k) の空間を使用します。 再帰解法では、1 つの完全なグループを確認して反転し、サフィックスに対して再帰を適用することで、O(n / k) のスタック空間を使用します。 空間計算量 O(1) を目指す場合、反復バージョンが適切な選択となります。迅速なレビューを優先する小規模な入力であれば、明示的なトレードオフとして スタックアプローチを採用することも妥当です。
テストでは、単に値の配列を比較する以上の検証が必要です。元のノード参照のセットを保存し、結果をトラバースして、 順序を確認する前に、サイクルがないこと、ノード数が一致すること、全く同じ参照が含まれていることをアサートします。 防御的な空入力、1 ノード、k = 1、n = k、割り切れる長さ、不完全な末尾、 重複値、最大サイズをカバーします。値のみのテストではノードオブジェクトが再利用されたかを証明できないため、重複値のテストは特に有用です。
質の高い模範解答
「まず、末尾の k 個未満のノードがそのままの順序を維持すること、および値の交換が不可であることを確認します。反復処理の状態は、 ダミーノードと固定数の参照で管理します。groupPrev は常に現在のグループの直前に配置します。そこから k ステップ進め、 kth が存在しない場合は、末尾のポインタを変更する前にリターンします。
完全なグループの場合、groupNext を保存します。prev を groupNext で初期化し、元のグループ先頭から groupNext に到達するまで標準的な 3 ポインタ反転を適用します。この初期化が重要です。元の先頭が末尾になったとき、 その next はすでに後続セグメントを指しています。反転後、kth が新しい先頭になります。 groupPrev.next をそこに接続し、groupPrev を元の先頭へ移動します。
不変条件として、処理済みプレフィックスは正しく接続されており、groupPrev.next は最初の未処理ノードであり、サフィックスは 入力順序を維持していることが保証されます。完全な反転によってプレフィックスが拡張され、不完全なグループでは書き込みが発生しないため末尾が保護されます。 各ノードは先読みで最大 1 回、反転で最大 1 回訪問されるため、時間計算量は O(n)、追加空間計算量は O(1) です。 値の並びだけでなく、ノードの同一性と非循環性も検証します。」
よくあるミス
- 完全グループを確認する前に反転を開始する → 不完全な末尾が変更され元に戻せなくなる →
最初に読み取り専用の先読みを実行する。
prev = nullで反転を開始する → グループがサフィックスから一時的に切り離され、切断されたままになりやすい →
prev = groupNext で開始する。
- 新しいグループ先頭のみを接続する → 新しい末尾がサフィックスに接続されない可能性がある →
groupNext を保持し、新しい末尾がそれを指していることを確認する。
kthを次の先行ポインタとして維持し続ける → 次のグループ境界が不正になる →
groupPrev を元のグループ先頭に移動する。
- ノードの値を交換する → ノードの同一性や付随するフィールドのセマンティクスが壊れる →
next のみを変更する。
- 再帰解法の補助空間を
O(1)だと主張する → グループ数に応じてコールスタックが増加する →
定数追加空間を達成するために反復処理を使用する。
- 値のシーケンスのみをテストする → ノードの欠落、コピー、サイクルの発生を見逃す可能性がある →
参照の同一性、ノード数、非循環性も検証する。
- 先読みと反転を掛け算して
O(nk)だと誤認する → 各反復で処理するグループは互いに重複しない →
ノードごとの総訪問回数を合算する。
フォローアップ質問と回答
フォローアップ 1: k 個未満の最後のグループも反転する必要がある場合はどうしますか？
先読みが失敗した際に直ちにリターンすることはできなくなります。残りのノード数を実際にカウントしてその短いセグメントを反転するか、 あるいはアルゴリズムの最初でリスト全体の長さを計算し、min(k, remaining) をグループサイズとして使用します。 不変条件の終了条件が変更され、n < k のケースの対応が必須となります。
フォローアップ 2: グループごとに交互に反転させるにはどうしますか？
完全な k 個のノードグループ単位で先読みを続け、boolean フラグを保持します。反転対象グループには元のロジックを適用し、 スキップするグループではポインタを変更せずに groupPrev を k ノード分進めます。不完全な末尾グループを スキップ対象とするか反転対象とするかで結果が変わるため、そのルールを再度確認する必要があります。
フォローアップ 3: アルゴリズムがサイクルを生成しないことをどのように証明しますか？
局所的な証明には 2 つの境界を用います。現在のグループ外にある groupNext を保存し、 prev = groupNext から current === groupNext まで反転を行います。書き換えられたすべてのエッジは、現在のノードからすでに処理済みの 先行ノードまたはサフィックスの進入点を指し、現在のグループ内の未処理部分を指し戻すことは決してありません。テストにおいても、 fast-slow ポインタによるサイクル検出を実行し、走査されたノード数が入力ノード数と一致することをアサートすべきです。
フォローアップ 4: リストが 1 億ノードある場合、何が変わりますか？
漸近的な計算量は同じですが、再帰を避け、ノードのコピーを行わず、長時間の単一操作に対するタイムアウトやキャンセル処理を 考慮する必要があります。リストが外部ストレージにある場合や複数マシンに分散している場合、ランダムな繋ぎ替えやアトミックな可視性の確保が 主要な課題となります。インメモリのアルゴリズムをそのまま適用することはできず、データ配置、トランザクション境界、回復可能なチェックポイントを まず定義する必要があります。