連結リストの中間ノードを削除する
単方向連結リストから中間ノードを削除する必要があります。中間ノードは、0ベースのインデックスを使用して ⌊n / 2⌋ 番目のノードとします。
効率的な解決方法は以下の通りです。
戦略
2つのポインタを使用して、1回の走査で中間を見つけます。
- 1ステップずつ進むスローポインタを使用します。
- 2ステップずつ進むファストポインタを使用します。
- ファストポインタが末尾に到達したとき、スローポインタは中間位置にあります。
- スローポインタの前のノードを追跡するために、3つ目のポインタを保持します。
ロジック
- エッジケースを処理します。リストにノードが1つしかない場合は、null を返します。
- スローポインタとファストポインタを head に初期化します。
- ファストポインタを2ステップ、スローポインタを1ステップ進めます。
- スローポインタの1つ後ろを維持するように prev ポインタを更新します。
- ループが終了したら、prev ノードを slow の次のノードにリンクします。これにより、中間ノードがスキップされます。
計算量
- 時間計算量: O(n)。リストを1回走査します。
- 空間計算量: O(1)。3つのポインタのみを使用します。
PHPによる実装
function deleteMiddle(ListNode $head): ?ListNode
{
if ($head->next == null) {
return null;
}
$slow = $head;
$fast = $head;
$prev = null;
while ($fast !== null && $fast->next !== null) {
$prev = $slow;
$slow = $slow->next;
$fast = $fast->next->next;
}
$prev->next = $slow->next;
return $head;
}
出典: https://dev.to/mdarifulhaque/2095-delete-the-middle-node-of-a-linked-list-4jf1