1. アルゴリズム概要
単方向連結リスト head を 1 回だけ走査し、値が < x のノードを less、それ以外を ge に 末尾追加（安定）。最後に less の末尾を ge の先頭へ連結します。
-
O(n) / 単一走査
比較と末尾追加のみ。
-
安定パーティション
相対順序を保持。
-
Pure（非破壊）
入力ノードは変更しない。
2. ステップバイステップ解説（視覚化付き）
-
1
Init dummies & tails
空の less / ge を作成
-
2
Single pass
cur を進めて分配を判断
-
3
Append to less (< x)
1, 2, 2 が less に入る
-
4
Append to ge (≥ x)
4, 3, 5 が ge に入る
-
5
Connect lists
less → ge
入力: [1, 4, 3, 2, 5, 2], x = 3
ステップをクリック / Play でアニメーション初期化：番兵（lessDummy / geDummy）とテール参照を用意。
3. コード例（Python / LeetCode形式）
from __future__ import annotations
from typing import Optional, TYPE_CHECKING
# Type-checking fallback (LeetCode env already provides ListNode)
if TYPE_CHECKING:
class ListNode:
def __init__(self, val: int = 0, next: Optional["ListNode"] = None) -> None: ...
val: int
next: Optional["ListNode"]
try:
ListNode # type: ignore[name-defined]
except NameError:
class ListNode:
__slots__ = ("val", "next")
def __init__(self, val: int = 0, next: Optional["ListNode"] = None) -> None:
self.val = val
self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
"""Stable partition of linked list around x (pure, non-destructive)."""
# 1) create dummies and tails
less_dummy = ListNode(0)
ge_dummy = ListNode(0)
lt_tail = less_dummy
ge_tail = ge_dummy
# 2) single pass: append new nodes
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
# 3) connect less -> ge
lt_tail.next = ge_dummy.next
ge_tail.next = None
return less_dummy.next4. 視覚的図解・フローチャート
5. 時間計算量
Time
O(n)
各ノードは 1 回だけ処理。
Space（本実装 / Pure）
O(n)
入力不変のため新ノードを構築。
Space（参考 in-place）
O(1)
破壊的再配線なら追加メモリは定数。