連結リストパターン

中級

カテゴリ: linked-lists

概要

連結リスト（Linked List）は、各要素（ノード）がデータと次のノードへの参照（ポインタ）を持つ線形データ構造です。単方向連結リスト、双方向連結リスト、循環連結リストなどの種類があります。配列と異なり、要素は連続したメモリ領域に格納されず、動的にサイズを変更できます。先頭や途中での挿入・削除が効率的（O(1)）ですが、特定のインデックスへのアクセスには O(n) の時間がかかります。

コードテンプレート

Java

Python

- 単方向連結リストのノード定義
class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

Java

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

ポインタ操作ノード次の参照ヘッドノードテールノード単方向リスト双方向リスト循環リストリスト反転サイクル検出交点検出中間ノードファストポインタスローポインタダミーヘッドポインタ操作

チャート式ひらめきポイント

問題を読んだときに、「ソート済み配列で何かを見つける」「二つの要素の関係を調べる」「効率的に配列を操作する」などの特徴があれば、双指針パターンが適用できる可能性が高いです。特に、O(n²)の計算量を避けたい場合に有効です。

このパターンを使用する問題例

1
連結リストの反転（Reverse Linked List）: 連結リストを逆順にする
2
連結リストのサイクル検出（Linked List Cycle）: 連結リスト内にサイクルが存在するかを判定する
3
2つの連結リストの交点（Intersection of Two Linked Lists）: 2つの連結リストが交差する最初のノードを見つける
4
連結リストの中間ノード（Middle of the Linked List）: 連結リストの中間ノードを見つける

このパターンを使う問題

このパターンを適用して解くことができる実際の問題です。

易

連結リストの反転

単方向連結リストの先頭を表すノード head が与えられたとき、リストを反転させて、反転したリストの先頭を返してください。...