アルゴリズム概要

O(n)
時間計算量
O(1)
空間計算量
0 〜 300
ノード数制約
-100〜100
値の範囲

問題の要点

ソート済み単方向連結リストの先頭ノード head を受け取り、 各要素がちょうど 1 回だけ現れるようにリストを変更して返す。
ソート済みであるという特性から、重複は必ず隣接して現れる。 これにより 1 パスの線形走査で解決できる。

入力例 1
head = [1, 1, 2]
出力: [1, 2]
入力例 2
head = [1, 1, 2, 3, 3]
出力: [1, 2, 3]
⚠️ 落とし穴
  • 🔸 重複スキップ後に current を進めてはいけない（3連続重複を見逃す）
  • 🔸 head is None と head.next is None の両方をガード
  • 🔸 新しいノードを作成しない — インプレースでポインタだけ付け替える

ステップバイステップ解説

実装コード

処理フローチャート

開始 / 終了
処理ノード
条件分岐
はい / 正常終了
重複検出
ループバック
flowchart TD Start([" 開始 "]) Guard["ガード節
head is None OR head.next is None ?"] GuardTrue["return head
変更なしで即時返却"] Init["初期化
current = head"] LoopCheck{"current.next
is not None ?"} Cache["nxt = current.next
次ノードをキャッシュ"] DupCheck{"current.val
== nxt.val ?"} Skip["nxt をスキップ
current.next = nxt.next
※ current は動かさない"] Advance["current を前進
current = nxt"] Return["return head
重複除去済みリストを返す"] End([" 終了 "]) Start --> Guard Guard -- "True
空 or 単一ノード" --> GuardTrue Guard -- "False
複数ノード存在" --> Init GuardTrue --> End Init --> LoopCheck LoopCheck -- "False
current.next が None
ループ終了" --> Return LoopCheck -- "True
次ノード存在" --> Cache Cache --> DupCheck DupCheck -- "True
重複あり" --> Skip DupCheck -- "False
重複なし" --> Advance Skip -- "再チェック
同じ current で
ループ先頭へ戻る" --> LoopCheck Advance -- "次ノードへ
ループ先頭へ戻る" --> LoopCheck Return --> End style Start fill:#d1fae5,stroke:#10b981,stroke-width:2px,color:#065f46 style End fill:#d1fae5,stroke:#10b981,stroke-width:2px,color:#065f46 style Guard fill:#e0f2fe,stroke:#0284c7,stroke-width:2px,color:#0c4a6e style GuardTrue fill:#d1fae5,stroke:#059669,stroke-width:2px,color:#065f46 style Init fill:#e0f2fe,stroke:#0284c7,stroke-width:2px,color:#0c4a6e style LoopCheck fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,color:#92400e style Cache fill:#f1f5f9,stroke:#64748b,stroke-width:2px,color:#1e293b style DupCheck fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,color:#92400e style Skip fill:#fee2e2,stroke:#dc2626,stroke-width:2px,color:#991b1b style Advance fill:#f1f5f9,stroke:#64748b,stroke-width:2px,color:#1e293b style Return fill:#d1fae5,stroke:#059669,stroke-width:2.5px,color:#065f46 linkStyle 0 stroke:#64748b,stroke-width:2px linkStyle 1 stroke:#059669,stroke-width:2px linkStyle 2 stroke:#64748b,stroke-width:2px linkStyle 3 stroke:#059669,stroke-width:2px linkStyle 4 stroke:#64748b,stroke-width:2px linkStyle 5 stroke:#059669,stroke-width:2px linkStyle 6 stroke:#64748b,stroke-width:2px linkStyle 7 stroke:#64748b,stroke-width:2px linkStyle 8 stroke:#dc2626,stroke-width:2px linkStyle 9 stroke:#64748b,stroke-width:2px linkStyle 10 stroke:#a855f7,stroke-width:2px,stroke-dasharray:6 4 linkStyle 11 stroke:#a855f7,stroke-width:2px,stroke-dasharray:6 4 linkStyle 12 stroke:#059669,stroke-width:2px
① ガード節（Guard）

リストが空(None)、またはノードが1つ(head.next is None)なら重複は存在しない。即 head を返して終了（緑の矢印）。

② ループ条件チェック

current.next is None になったらループ終了（緑矢印 → return）。
current.next が存在する間は内部処理を継続（下方向）。

③ 重複検出 → Skip（赤矢印）

current.val == nxt.val なら current.next = nxt.next で nxt を切り離す。current は移動せず、ループ先頭へ戻って再チェック（紫の破線）。

④ 値が異なる → Advance（紫破線）

current.val != nxt.val なら current = nxt で1つ前進。ループ先頭へ戻って次のノードを比較（紫の破線）。

計算量分析

指標 値 理由
時間計算量 O(n) 各ノードを最大 1 回走査。重複スキップ時も current は移動しないが、next の参照が前進するため全体では O(n)
空間計算量 O(1) スタック変数 current / nxt のみ。新規ノード生成ゼロ
ヒープ確保 0 回 既存ノードの next 付け替えのみ。新オブジェクト生成なし

アプローチ比較

アプローチ Time Space 特徴
✅ 1ポインタ・インプレース（本実装） O(n) O(1) 最適。ヒープ確保ゼロ
再帰 O(n) O(n) 可読性高いがコールスタック消費
配列変換＋再構築 O(n) O(n) 不要なオブジェクト生成多数