連結リストのその場操作
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 / よくある落とし穴
next を保存する前に残りのリストを失う。
元の
curr.next を保存する前に curr.next ← prev と 反転してしまうと、後続が切り離されてしまう。保存のステップは省けない —— ポインタが 3 つある理由はまさにこれ。返り値を間違える。
ループ終了時、
curr は null で、prev が新しい先頭。curr を返してしまうと空でないリストに対しても null が返る —— ありがちな取り違え。空リストを扱い忘れる。
head = null ではループ本体は実行されず、prev は null のまま。これは正しい —— ただしループに入らないからこそ正しい。 空の場合を明示的に確認すること。ガードの前に curr.next を覗くと、 ヌル参照を簡単に作り込んでしまう。05 / LeetCode で練習
簡単9
01Merge Two Sorted Lists— LC 21→02Remove Duplicates from Sorted List— LC 83→03Linked List Cycle— LC 141→04Intersection of Two Linked Lists— LC 160→05Remove Linked List Elements— LC 203→06Reverse Linked List— LC 206→07Palindrome Linked List— LC 234→08Middle of the Linked List— LC 876→09Convert Binary Number in a Linked List to Integer— LC 1290→
中級33
01Add Two Numbers— LC 2→02Remove Nth Node From End of List— LC 19→03Swap Nodes in Pairs— LC 24→04Rotate List— LC 61→05Remove Duplicates from Sorted List II— LC 82→06Partition List— LC 86→07Reverse Linked List II— LC 92→08Convert Sorted List to Binary Search Tree— LC 109→09Flatten Binary Tree to Linked List— LC 114→10Populating Next Right Pointers in Each Node— LC 116→11Populating Next Right Pointers in Each Node II— LC 117→12Copy List with Random Pointer— LC 138→13Linked List Cycle II— LC 142→14Reorder List— LC 143→15LRU Cache— LC 146→16Sort List— LC 148→17Delete Node in a Linked List— LC 237→18Odd Even Linked List— LC 328→19Plus One Linked List— LC 369→20Linked List Random Node— LC 382→21Flatten a Multilevel Doubly Linked List— LC 430→22Add Two Numbers II— LC 445→23Design Linked List— LC 707→24Split Linked List in Parts— LC 725→25Next Greater Node In Linked List— LC 1019→26Remove Zero Sum Consecutive Nodes from Linked List— LC 1171→27Print Immutable Linked List in Reverse— LC 1265→28Linked List in Binary Tree— LC 1367→29Merge In Between Linked Lists— LC 1669→30Swapping Nodes in a Linked List— LC 1721→31Reverse Nodes in Even Length Groups— LC 2074→32Delete the Middle Node of a Linked List— LC 2095→33Maximum Twin Sum of a Linked List— LC 2130→