リンクリストの反転｜コードで実践

リンクリストの反転

このレッスンで分かること

result.insert(0, value) は「先頭に追加する」操作で、本物のリンクリストでいう new_node.next = head; head = new_node に対応します

リンクリストの反転は、連結リスト系の問題で 最も基本かつ重要 なテーマです

ただし「アルゴリズムの考え方」は配列でも本物のリストでも同じです

リンクリストの反転とは

配列で表現された連結リストを反転させ、ポインタ付け替えのアルゴリズムを身につける。本レッスンでは、リンクリストの反転の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

リンクリストの反転は、連結リスト系の問題で 最も基本かつ重要 なテーマです。1 -> 2 -> 3 -> null を 3 -> 2 -> 1 -> null に変える操作で、技術面接でも頻出します。本物のリンクリストでやる場合は、各ノードの next ポインタを順番に付け替えていくのですが、本コースでは配列表現を採用しているため、配列を逆順にして返せば OK です。

ただし「アルゴリズムの考え方」は配列でも本物のリストでも同じです。3 つのポインタ prev、curr、next を使って付け替えていく、というのが定石です。これを配列の世界に翻訳すると、result という新しい配列を用意し、元の配列を後ろから順に詰めていく、または先頭に追加していく形になります。

ポインタの付け替えは 3 ステップ で覚える。next を保存 → curr の next を prev に → prev と curr を進める。

ビジュアルで理解する

diagram (will load when visible)

図のポイント (テキスト併記)

上半分が反転前、下半分が反転後です

上半分が反転前、下半分が反転後です。各ノードの next が逆向きに付け替わっていることが分かります。

Python での実装

配列表現での反転は、Python なら arr[::-1] で 1 行ですが、ここでは 連結リストの反転アルゴリズムを意識して 書きます。

Python

def reverseList(arr):
    result = []
    for value in arr:
        result.insert(0, value)
    return result

result.insert(0, value) は「先頭に追加する」操作で、本物のリンクリストでいう new_node.next = head; head = new_node に対応します。元のリストを 1 ノードずつ前に追加していくと、最後には反転したリストになります。なお O(n^2) になるので、本物のリストでは prev / curr / next を使った O(n) 版が普通です。

JavaScript での実装

JavaScript

function reverseList(arr) {
  const result = [];
  for (const value of arr) {
    result.unshift(value);
  }
  return result;
}

JavaScript の unshift も insert(0, ...) と同様、配列の先頭に要素を追加します。return arr.slice().reverse() でも結果は同じです。

よくある間違い

1 つ目は 元の配列を破壊 してしまうケースです。arr.reverse() は元の配列自体を変更します。テストで他の処理に影響することがあるので、必要なら arr.slice().reverse() を使います。2 つ目は 空配列を返し忘れる こと。空リストを反転しても空リストです。if not arr: return [] のような早期 return を入れるか、自然に空配列が返ることを確認します。3 つ目は 本物のリストで next を保存し忘れる ことです。curr.next = prev を先にやると、元の next が失われて先に進めなくなります。

やってみよう

[1, 2, 3] を渡したら [3, 2, 1] が返るか確認する。
空配列 [] を渡したら [] が返るか確認する。
本物のリンクリスト (ノードクラス) で同じ処理を書いてみる。prev = None、curr = head から始めて、while curr: で next = curr.next; curr.next = prev; prev = curr; curr = next を回す形になる。

反復版と再帰版

本物のリンクリスト反転には 反復版 と 再帰版 の 2 つの定石があります。反復版は前述の prev / curr / next を while で回す方法で、O(n) 時間 / O(1) 空間です。再帰版は「自分の next から先を反転してもらい、自分は末尾に付け足してもらう」という発想で、コードは短いものの コールスタックを n 個積む ため O(n) 空間になります。技術面接では O(1) 空間を求められることが多いので、反復版を覚えておくのが安全です。

Python

# 再帰版の例 (本物のノード構造)
def reverse(head):
    if not head or not head.next:
        return head
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head

再帰版の理解には少し慣れが必要ですが、head.next.next = head の 1 行が「自分を末尾に付け足す」操作です。

反復版は O(1) 空間、再帰版は O(n) 空間。本番では基本的に 反復版 を選ぶ。

反転が応用される場面

反転は単体で使うより、より大きな問題の部品として登場します。例えば「リンクリストが回文かを判定する」問題では、中央で分割して後半を反転し、前半と比較します。「k 個ずつグループで反転する」問題でも、部分反転 が中心テクニックです。本章のあとの章でも merge sort の merge ステップなどでポインタの付け替えを思い出してください。

反転は 基本テクニック。回文判定、グループ反転など、多くの応用問題の前処理として登場する。

反転は ポインタの 3 ステップ付け替え が基本。配列表現でも頭の中ではノードを意識する。

よくある質問

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 が定型問題なので解いておくと良いです。

次のレッスン

次は リンクリストのサイクル検出 で、リストにループ(循環)があるかを 2 ポインタ法で判定する方法を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

リンクリスト反転の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. リンクリスト反転とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

リンクリストの反転