アルゴリズム概要

Dummy Node + Two Pointers Technique

ソート済み連結リストの特性を活かし、ダミーノードと2つのポインタを使用して重複要素を効率的に削除する手法です。

問題の要求事項

  • ソート済み連結リストが入力として与えられる
  • 重複する値を持つノードはすべて削除する
  • 一意な値を持つノードのみを残す
  • 結果もソート済みの状態を維持する

解法の核心

  • ダミーノード: 先頭削除の場合も統一的に処理
  • Two Pointers: prev（安全な位置）とcurr（探索位置）
  • 重複検出: curr.val == curr.next.valで判定
  • スキップ処理: 同値ノードをすべて飛ばす

アルゴリズムの特徴

  • 時間計算量： O(n) - 各ノードを一度だけ走査
  • 空間計算量： O(1) - 追加のデータ構造不要
  • 安定性： ソート順を維持
  • 効率性： インプレース操作

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

1
ダミーノードの初期化

処理を簡潔にするためダミーノードを作成し、元のheadに接続します。prevポインタをダミーノードに設定。

2
重複の検出

currノードの値とcurr.nextノードの値を比較し、重複があるかチェックします。

3
重複ノードのスキップ

重複が見つかった場合、同じ値を持つすべてのノードをスキップしてcurrを進めます。

4
リンクの再構築

prev.nextをcurrに設定し、重複ノードを除外したリンクを構築します。

5
ポインタの更新

重複がない場合はprevとcurrの両方を次に進め、重複がある場合はcurrのみ進めます。

実行例：[1,2,3,3,4,4,5] → [1,2,5]

dummy
→
1
→
2
→
3
→
3
→
4
→
4
→
5

実装コード

solution_competitive.py 
from typing import Optional

class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None) -> None:
        self.val: int = val
        self.next: Optional["ListNode"] = next

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """
        Time Complexity: O(n)  - 各ノードを一度だけ走査
        Space Complexity: O(1) - ポインタ操作のみ
        """
        dummy = ListNode(0, head)  # ダミーノード作成
        prev = dummy  # 最後に確定したユニーク要素の直前
        curr = head

        while curr:
            # 重複チェック
            if curr.next and curr.val == curr.next.val:
                # 重複値を保存
                dup_val = curr.val
                # 同じ値のノードをすべてスキップ
                while curr and curr.val == dup_val:
                    curr = curr.next
                # 重複ノードを飛ばして接続
                prev.next = curr
            else:
                # 重複なしの場合、ポインタを進める
                prev = curr
                curr = curr.next

        return dummy.next
solution_production.py 
from typing import Optional

class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None) -> None:
        self.val: int = val
        self.next: Optional["ListNode"] = next

class Solution:
    def deleteDuplicates_safe(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """
        型安全・エラーハンドリング付きの堅牢版

        Args:
            head: 連結リストの先頭ノード

        Returns:
            重複を除去した連結リストの先頭ノード

        Raises:
            TypeError: headがListNodeまたはNoneでない場合
        """
        # 入力検証
        if head is not None and not isinstance(head, ListNode):
            raise TypeError("head must be a ListNode or None")

        # エッジケース処理
        if head is None or head.next is None:
            return head

        dummy = ListNode(0, head)
        prev = dummy
        curr = head

        while curr:
            if curr.next and curr.val == curr.next.val:
                dup_val = curr.val
                # 重複ノードを安全にスキップ
                while curr and curr.val == dup_val:
                    curr = curr.next
                prev.next = curr
            else:
                prev = curr
                curr = curr.next

        return dummy.next

計算量解析

時間計算量
O(n)

各ノードを最大で一度だけ走査するため、線形時間で処理が完了します。

空間計算量
O(1)

ダミーノードと数個のポインタ変数のみ使用。入力サイズに依存しない定数空間。

パフォーマンス特性

  • 最良の場合： 重複なし → O(n)時間で全ノードを一度走査
  • 最悪の場合： 全て重複 → O(n)時間で全ノードを削除
  • 平均の場合： 部分的重複 → O(n)時間で効率的処理
  • メモリ効率： インプレース操作でメモリ使用量を最小化