アルゴリズム概要
連結リストを閾値
x
で安定パーティションします。x 未満のノードを前に、x
以上のノードを後に配置し、各パーティション内の相対順序を保持します。
採用アルゴリズム: 非破壊コピー方式
- 2本のリスト（less, greater_equal）を並行構築
- 元データを変更しない（Pure関数）
- 単一走査でO(n)時間計算量
- 安定性を自動保証
入力例
[1,4,3,2,5,2], x = 3
出力例
[1,2,2,4,3,5]
ステップバイステップ解説
Step 1: 初期化
ダミーノードとテールポインタを初期化
Step 2: Less リスト構築
x未満の要素をlessリストに追加
Step 3: GE リスト構築
x以上の要素をgeリストに追加
Step 4: リスト連結
lessリストの末尾をgeリストの先頭に接続
Step 5: 完了
最終的なパーティション済みリストを返却
Python実装 (LeetCode形式)
from __future__ import annotations
from typing import Optional, TYPE_CHECKING
# Pylance対応のフォールバック定義
if TYPE_CHECKING:
class ListNode:
def __init__(self, val: int = 0, next: Optional["ListNode"] = None) -> None: ...
val: int
next: Optional["ListNode"]
else:
class ListNode:
__slots__ = ("val", "next")
def __init__(self, val: int = 0, next: Optional["ListNode"] = None) -> None:
self.val = val
self.next = next
class Solution:
"""
Partition List (安定パーティション)
- 非破壊（Pure）：入力ノードは変更せず、新ノードを生成
- (< x) が前、(>= x) が後。元の相対順序は維持（安定）
"""
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
"""
Args:
head: 連結リスト先頭
x: しきい値
Returns:
パーティション後の新しい連結リスト先頭（非破壊）
Complexity:
Time: O(n) — n はノード数（単一走査）
Space: O(n) — Pureのため新ノードを生成
"""
# ダミー（番兵）とテール
less_dummy = ListNode(0)
ge_dummy = ListNode(0)
lt_tail = less_dummy
ge_tail = ge_dummy
cur = head
while cur is not None:
v = cur.val # 属性参照を一度だけ
if v < x:
lt_tail.next = ListNode(v)
lt_tail = lt_tail.next
else:
ge_tail.next = ListNode(v)
ge_tail = ge_tail.next
cur = cur.next
# 連結（less -> ge）
lt_tail.next = ge_dummy.next
ge_tail.next = None
return less_dummy.next
実装のポイント
- ダミーノード活用：分岐処理を削減し、コードを簡潔化
-
属性アクセス最小化：
cur.valを変数vに一度だけ取得 - Pure関数：元データを変更せず、新しいノードを生成
-
型安全性：
Optional[ListNode]で null安全性を確保
アルゴリズムフローチャート
このフローチャートは、連結リストを閾値xで安定パーティションするアルゴリズムの処理フローを示しています
Less List (< x)
閾値未満の要素を順序保持して構築
GE List (≥ x)
閾値以上の要素を順序保持して構築
Final Connection
2つのリストを連結して完成
計算量解析
時間計算量: O(n)
単一走査：元リストを1回だけ巡回
定数時間操作：各ノードに対する判定・追加処理
最適性：これ以上の効率化は不可能
空間計算量: O(n)
新ノード生成：各元ノードに対応
非破壊的：元データを保護（Pure関数）
補助構造：ダミーノード2個（定数）
アルゴリズム比較
| アプローチ | 時間計算量 | 空間計算量 | 特徴 |
|---|---|---|---|
| 非破壊コピー（採用） | O(n) | O(n) | 安全・Pure・可読性高 |
| 破壊的再配線 | O(n) | O(1) | 最速・省メモリ |
| 安定ソート | O(n log n) | O(n) | 過剰計算 |
| 逐次挿入 | O(n²) | O(1) | 実用性低 |
採用理由
非破壊コピー方式は、最適な時間計算量O(n)を保ちながら、元データの安全性と高い可読性を両立。 業務開発における保守性と競技プログラミングにおける効率性の両方を満たす実装です。