ソート済みリストの重複削除｜コードで実践

ソート済みリストの重複削除

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

末尾要素との比較だけで OK

本物の連結リストでは、上記のように curr.next = curr.next.next で 既存のリストを直接書き換える in-place 版が最も効率的です

ソート済みの連結リストから連続する重複を取り除く操作は、データ整形でよく使われる前処理です

ソート済みリストの重複削除とは

ソート済み連結リストから連続する重複ノードを除去し、in-place な編集の発想を身につける。本レッスンでは、ソート済みリストの重複削除の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

ソート済みの連結リストから連続する重複を取り除く操作は、データ整形でよく使われる前処理です。例えばログの時系列データから同じイベントを 1 件に集約するときや、ユーザー ID の一覧を unique にするときに登場します。

本コースの配列表現でいうと、[1, 1, 2, 3, 3] を受け取って [1, 2, 3] を返す関数を作ります。Python なら set を使う手もありますが、それだと 順序が崩れる 可能性があるので、ソート済みであることを活かして 1 パスで隣り合う要素を比較 する方法が定石です。

ソート済みなら 重複は必ず隣に並ぶ。隣との比較だけで重複を検出できる。

1 パス処理のアイデア

結果配列 result を用意し、元の配列を頭から見ていきます。「result の末尾」と「現在見ている要素」が違うときだけ、現在の要素を result に追加します。最初の要素は無条件に追加する、というのがコツです。

末尾要素との比較だけで OK。result[-1] != arr[i] を判定条件にする。

ビジュアルで理解する

diagram (will load when visible)

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

隣り合う重複を消した結果が [1, 2, 3] です

隣り合う重複を消した結果が [1, 2, 3] です。連続していない重複 (例えば [1, 2, 1]) はこの方法では削除されませんが、ソート済み前提なのでそういうケースは発生しません。

Python での実装

Python

def removeDuplicates(arr):
    if not arr:
        return []
    result = [arr[0]]
    for i in range(1, len(arr)):
        if arr[i] != result[-1]:
            result.append(arr[i])
    return result

空配列の早期 return がポイントです。空でなければ最初の要素を result に入れて、2 番目以降は末尾と比較しながら追加していきます。set(arr) でも重複は除けますが、順序の保証がないため、ソート済みの順序を維持したい場面では使えません。

JavaScript での実装

JavaScript

function removeDuplicates(arr) {
  if (arr.length === 0) return [];
  const result = [arr[0]];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] !== result[result.length - 1]) {
      result.push(arr[i]);
    }
  }
  return result;
}

result[result.length - 1] で末尾要素にアクセスします。result.at(-1) でも書けますが、互換性のため [length - 1] が無難です。

よくある間違い

1 つ目は 末尾比較の対象を間違える ことです。arr[i - 1] と arr[i] を比べると、削除した直後の要素が抜けて連続性が崩れます。必ず result の末尾と比較します。2 つ目は 空配列の扱い です。arr[0] でアクセスすると IndexError や undefined が出るので、最初に空チェックを入れます。3 つ目は ソートされていない入力。ソートされていない [1, 2, 1] を入れると重複が除去されません。本レッスンではソート済みを仮定します。

やってみよう

[1, 1, 2, 3, 3] を渡したら [1, 2, 3] が返るか確認する。
[1, 1, 1] を渡したら [1] が返るか確認する。
本物のリンクリストで書いてみる。curr = head; while curr and curr.next: if curr.val == curr.next.val: curr.next = curr.next.next; else: curr = curr.next の形で in-place に書ける。

in-place 版と新規配列版

本物の連結リストでは、上記のように curr.next = curr.next.next で 既存のリストを直接書き換える in-place 版が最も効率的です。O(1) 空間で済みます。一方、配列で実装する場合は、新しい配列 result を用意する方が分かりやすく安全です。O(n) 空間にはなりますが、元データを壊さないため副作用がありません。

副作用を許容するか、元のデータを保つかは設計判断です。実務では 関数型プログラミング の流儀に従い、新規配列を返す方が安全で、テストもしやすいです。set で実装すると順序が崩れるため、順序を保つ重複除去 という要件があるときは本レッスンの方法を選んでください。

in-place 版は O(1) 空間で効率的。新規配列版は副作用なしで安全。要件次第で使い分ける。

よくある質問

Q. この内容は面接でよく聞かれますか？

A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。

Q. 計算量と空間計算量はどっちを優先しますか？

A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。

Q. 問題が解けないときどう取り組めば良いですか？

A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。

次のレッスン

次は 第1章まとめクイズ で、ソート済み連結リストから連続する重複ノードを除去し、in-place な編集の発想を身につけるを学びます。

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

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

理解度チェック (30 秒)

Q. 重複ノード削除とは何か、1 文で説明してください。

この章のポイント

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

関連レッスン

ソート済みリストの重複削除