リンクリストの中央ノード取得
リンクリストの中央ノード取得
このレッスンで分かること
- もう一つの中央取得方法として、2 パス版 があります
- 連結リストの 中央ノード を取得する操作は、
merge sortでリストを 2 等分するときや、回文判定で前半と後半を比較するときに使われる、頻出のテクニックです- 本コースは配列表現を使っているため、本質的には
arr[len(arr) // 2]で答えが出ますが、2 ポインタ法の感覚 を掴むため、slowを 1 歩、fastを 2 歩進めながら処理するイメージを意識し…
リンクリストの中央ノード取得 とは
slow / fast の 2 ポインタ法を使って連結リストの中央ノードの値を一発で取得する。本レッスンでは、リンクリストの中央ノード取得 の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
連結リストの 中央ノード を取得する操作は、merge sort でリストを 2 等分するときや、回文判定で前半と後半を比較するときに使われる、頻出のテクニックです。配列なら arr[len(arr) // 2] で一発ですが、本物のリンクリストでは長さを知るために一度全部辿る必要があります。これを 1 パスで取得できるのが 2 ポインタ法 です。
本コースは配列表現を使っているため、本質的には arr[len(arr) // 2] で答えが出ますが、2 ポインタ法の感覚 を掴むため、slow を 1 歩、fast を 2 歩進めながら処理するイメージを意識して書きましょう。fast が末尾に着いたとき、slow はちょうど中央にいます。
中央取得は slow / fast 2 ポインタ で 1 パス。
fastが末尾ならslowは中央。
偶数長と奇数長の扱い
リストの長さが奇数なら中央は 1 つに決まります。[1, 2, 3, 4, 5] なら中央は 3 です。偶数長の場合は 2 つあって [1, 2, 3, 4] なら中央は 2 か 3 のどちらか。本レッスンでは 後ろ側 を採用し、3 を返すルールにします (LeetCode の標準的な定義と同じ)。
偶数長で中央が 2 つあるときは 後ろ側 を採用するのが慣例。
[1,2,3,4]の中央は3。
ビジュアルで理解する
図のポイント (テキスト併記)
slowは 1 歩ずつ、fastは 2 歩ずつ進みます
slow は 1 歩ずつ、fast は 2 歩ずつ進みます。fast がリストの末尾に達した瞬間、slow はリストの中央を指しています。
Python での実装
Python
def middleNode(arr):
slow = 0
fast = 0
while fast < len(arr) and fast + 1 < len(arr):
slow += 1
fast += 2
return arr[slow]slow と fast をインデックスとして使い、fast + 1 < len(arr) の条件で 2 歩進めるかをチェックします。奇数長のとき fast はちょうど末尾インデックスで止まり、偶数長のとき fast は末尾を 1 つ超えた時点で while を抜けます。どちらの場合も slow は後ろ側の中央を指します。
JavaScript での実装
JavaScript
function middleNode(arr) {
let slow = 0;
let fast = 0;
while (fast < arr.length && fast + 1 < arr.length) {
slow += 1;
fast += 2;
}
return arr[slow];
}JavaScript も同じです。arr[Math.floor(arr.length / 2)] でも答えは合いますが、fast を 2 歩進める感覚を slow / fast 法 として体に染み込ませましょう。
よくある間違い
1 つ目は fast の境界条件 です。fast + 1 < len を忘れると、リストの末尾を 1 つ越えたところで arr[fast + 1] を読もうとしてエラーになります。本物のリンクリストでも fast.next is not None と fast.next.next is not None の両方を確認する必要があります。2 つ目は 偶数長の中央 をどちらにするかの曖昧さです。前半と後半どちらを返すか、仕様で決めておきます。3 つ目は 空リストの扱い です。空リストには中央がないので、本来は例外を投げるか None を返します。本レッスンでは長さ 1 以上を仮定します。
やってみよう
[1, 2, 3, 4, 5]を渡したら3が返るか確認する。[1, 2, 3, 4]を渡したら3(後ろ側) が返るか確認する。- 本物のリンクリストで書いてみる。
slow = head; fast = head; while fast and fast.next: slow = slow.next; fast = fast.next.next; return slow.valの形になる。
2 パス版との比較
もう一つの中央取得方法として、2 パス版 があります。最初のパスでリストの長さを数え、2 番目のパスで length / 2 個進む、というやり方です。O(n) 時間で同じ結果が得られますが、2 回リストを辿るためロスがあります。1 パスで取れる 2 ポインタ法の方が美しい とされ、面接でも好まれます。
Python
# 2 パス版 (参考)
def middle2pass(arr):
length = len(arr)
return arr[length // 2]配列なら len が O(1) なので 2 パス版もほぼノーコストですが、本物の連結リストでは length 取得自体が O(n) なので、1 パス版の優位性が際立ちます。
配列なら 2 パス版でもほぼ無料。連結リストでは 1 パスの 2 ポインタ法 が必須テクニック。
slow / fast パターンの応用
slow / fast の 2 ポインタは中央取得だけでなく、サイクル検出 (この章で学んだレッスン) や 末尾から k 番目 の取得、回文判定 の前処理など、応用が広いパターンです。覚えておくと一気に解ける問題が増えます。
例えば「末尾から k 番目のノード」を取得するには、fast を先に k 歩進めてから slow と一緒に末尾まで進める、というテクニックがあります。これも 1 パスで取れる賢い方法です。
slow / fastは 連結リストの万能パターン。中央 / k 番目 / サイクル / 回文、すべて応用できる。
中央取得は 回文判定 や merge sort の前段で必須。
slow / fastパターンは応用が広い。
よくある質問
Q. リンクリストと配列はどう使い分けますか？
A. 配列はランダムアクセス O(1)、リンクリストは先頭への追加 O(1) が強みです。ほとんどの実用ケースで配列の方が速く、リンクリストはアルゴリズム問題の練習や特殊用途（OS のスケジューラ等）で使われる程度です。
Q. サイクル検出はどう実装しますか？
A. Floyd の循環検出（2 ポインタ法、tortoise and hare）が定番です。slow を 1 ステップ、fast を 2 ステップ進めると、ループがあれば必ず同じノードで出会います。空間 O(1) で動くのが優秀な点です。
Q. リンクリストを反転するコツは？
A. prev, curr, next の 3 ポインタを使い、curr.next = prev で 1 個ずつ繋ぎ替えます。再帰版でも書けますが、反復版の方がスタック消費が無く安全です。LeetCode の Reverse Linked List が定型問題なので解いておくと良いです。
次のレッスン
次は ソート済みリストの重複削除 で、ソート済み連結リストから重複ノードを除去し、リストを in-place で編集する手法を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 中央ノード取得 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 中央ノード取得 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 連結リストは配列 arr (長さ 1 以上) で表現する
- slow / fast 2 ポインタ法を使って 1 パスで取得すること
- 偶数長のときは後ろ側の中央を返す (例: [1,2,3,4] -> 3)
入出力例
test-cases.txt
middleNode([1,2,3,4,5]) → 3
middleNode([1,2,3,4]) → 3
middleNode([1]) → 1
middleNode([1,2]) → 2
middleNode([10,20,30]) → 20
middleNode([1,2,3,4,5,6]) → 4