連結リストのその場操作
01 / 一文での本質
連結リストを其場で書き換えるには、3 つのポインタ prev、curr、next で歩む —— 反転の前に保存し、反転の後に進める。残りのリストは各ステップで常に到達可能のまま。
問題単方向連結リストを其場で反転する入力[1 → 2 → 3 → 4 → 5]
3 つのポインタ:prev は null、curr は先頭。next は各ステップで元のポインタを保存する。
ステップ
0 / 16
prev
null
curr
1 [0]
動作
init
0 / 16
02 / パターンの骨格
# 単方向連結リストを反転するprev ← nullcurr ← headwhile curr ≠ null:next ← curr.next // 1. 保存curr.next ← prev // 2. 反転prev ← curr // 3. prev を進めるcurr ← next // 4. curr を進めるreturn prev // 新しい先頭
03 / このパターンを使うべき合図
「其場で / O(1) 空間」
別のリストを作るのを禁じる制約 —— 既存のノードをつなぎ替える必要がある。 そこで多ポインタの操作が力を発揮する。
「反転 / 並べ替え」
変えるのはリストの構造であり、値ではない。値はそのまま、変わるのは
.next の向き。「部分リスト / 範囲」
リスト全体ではなく、2 つの位置の間の区間だけを反転する。アルゴリズムは同じ、 境界での縫い合わせが加わるだけ。
「マージ / 交互」
2 本のリストを 1 本にする(交互、あるいはソート順)。「ダミーヘッド」のテクニックで 先頭の境界処理が単純になる —— 最後に
dummy.next から拾い上げる。04 / よくある落とし穴
i.
next を保存する前に残りのリストを失う。
元の
curr.next を保存する前に curr.next ← prev と 反転してしまうと、後続が切り離されてしまう。保存のステップは省けない —— ポインタが 3 つある理由はまさにこれ。ii.
返り値を間違える。
ループ終了時、
curr は null で、prev が新しい先頭。curr を返してしまうと空でないリストに対しても null が返る —— ありがちな取り違え。iii.
空リストを扱い忘れる。
head = null ではループ本体は実行されず、prev は null のまま。これは正しい —— ただしループに入らないからこそ正しい。 空の場合を明示的に確認すること。ガードの前に curr.next を覗くと、 ヌル参照を簡単に作り込んでしまう。05 / LeetCode で練習
4 問。最初の 2 問は形を変えた反転。3 問目は定番のマージ。 4 問目はポインタの曲芸が本格的に効いてくる場面。