class ListNode:
    """単方向連結リストのノード"""
    __slots__ = ('val', 'next')  # メモリ効率のためスロットを使用
 
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
    def __repr__(self):
        return f"ListNode({self.val})"

class ListNode:
    """単方向連結リストのノード"""
    __slots__ = ('val', 'next')
 
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
    def __repr__(self):
        return f"ListNode({self.val})"
 
 
class SinglyLinkedList:
    """単方向連結リストの完全実装"""
 
    def __init__(self):
        self.head = None
        self._size = 0
 
    def __len__(self):
        return self._size
 
    def __iter__(self):
        """イテレータプロトコルの実装"""
        curr = self.head
        while curr:
            yield curr.val
            curr = curr.next
 
    def __repr__(self):
        values = []
        curr = self.head
        count = 0
        while curr and count < 20:  # 無限ループ防止
            values.append(str(curr.val))
            curr = curr.next
            count += 1
        chain = " -> ".join(values)
        if curr:
            chain += " -> ..."
        return f"SinglyLinkedList([{chain}])"
 
    def is_empty(self):
        """空リスト判定: O(1)"""
        return self.head is None
 
    def prepend(self, val):
        """先頭に挿入: O(1)"""
        self.head = ListNode(val, self.head)
        self._size += 1
 
    def append(self, val):
        """末尾に挿入: O(n)"""
        new_node = ListNode(val)
        if not self.head:
            self.head = new_node
        else:
            curr = self.head
            while curr.next:
                curr = curr.next
            curr.next = new_node
        self._size += 1
 
    def insert_at(self, index, val):
        """指定インデックスに挿入: O(n)
 
        Args:
            index: 挿入位置（0-based）。0 なら先頭、size なら末尾。
            val: 挿入する値
 
        Raises:
            IndexError: インデックスが範囲外の場合
        """
        if index < 0 or index > self._size:
            raise IndexError(f"Index {index} out of range [0, {self._size}]")
        if index == 0:
            self.prepend(val)
            return
        curr = self.head
        for _ in range(index - 1):
            curr = curr.next
        curr.next = ListNode(val, curr.next)
        self._size += 1
 
    def delete(self, val):
        """指定値の最初の出現を削除: O(n)
 
        Args:
            val: 削除する値
 
        Returns:
            bool: 削除に成功した場合 True、値が見つからなかった場合 False
        """
        # ダミーヘッドテクニックで先頭削除の特殊ケースを回避
        dummy = ListNode(0, self.head)
        curr = dummy
        while curr.next:
            if curr.next.val == val:
                curr.next = curr.next.next
                self.head = dummy.next
                self._size -= 1
                return True
            curr = curr.next
        return False
 
    def delete_at(self, index):
        """指定インデックスの要素を削除: O(n)
 
        Args:
            index: 削除位置（0-based）
 
        Returns:
            削除された値
 
        Raises:
            IndexError: インデックスが範囲外の場合
        """
        if index < 0 or index >= self._size:
            raise IndexError(f"Index {index} out of range [0, {self._size - 1}]")
        if index == 0:
            val = self.head.val
            self.head = self.head.next
            self._size -= 1
            return val
        curr = self.head
        for _ in range(index - 1):
            curr = curr.next
        val = curr.next.val
        curr.next = curr.next.next
        self._size -= 1
        return val
 
    def search(self, val):
        """値の検索: O(n)
 
        Returns:
            int: 値が見つかった場合そのインデックス、見つからない場合 -1
        """
        curr = self.head
        index = 0
        while curr:
            if curr.val == val:
                return index
            curr = curr.next
            index += 1
        return -1
 
    def get(self, index):
        """インデックスでアクセス: O(n)
 
        Args:
            index: 取得位置（0-based）
 
        Returns:
            指定位置の値
 
        Raises:
            IndexError: インデックスが範囲外の場合
        """
        if index < 0 or index >= self._size:
            raise IndexError(f"Index {index} out of range [0, {self._size - 1}]")
        curr = self.head
        for _ in range(index):
            curr = curr.next
        return curr.val
 
    def reverse(self):
        """リストを反転（in-place）: O(n)"""
        prev = None
        curr = self.head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        self.head = prev
 
    def to_list(self):
        """Python リストに変換: O(n)"""
        return list(self)
 
    @classmethod
    def from_list(cls, values):
        """Python リストから連結リストを構築: O(n)
 
        Args:
            values: イテラブルな値の列
 
        Returns:
            SinglyLinkedList: 構築された連結リスト
        """
        ll = cls()
        for val in reversed(values):
            ll.prepend(val)
        return ll
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    # 構築
    ll = SinglyLinkedList.from_list([1, 2, 3, 4, 5])
    print(ll)                   # SinglyLinkedList([1 -> 2 -> 3 -> 4 -> 5])
    print(f"Length: {len(ll)}")  # Length: 5
 
    # 挿入
    ll.prepend(0)
    ll.append(6)
    ll.insert_at(3, 99)
    print(ll)  # SinglyLinkedList([0 -> 1 -> 2 -> 99 -> 3 -> 4 -> 5 -> 6])
 
    # 検索
    print(f"Search 99: index {ll.search(99)}")  # Search 99: index 3
    print(f"Get index 3: {ll.get(3)}")          # Get index 3: 99
 
    # 削除
    ll.delete(99)
    deleted = ll.delete_at(0)
    print(f"Deleted: {deleted}")  # Deleted: 0
    print(ll)                     # SinglyLinkedList([1 -> 2 -> 3 -> 4 -> 5 -> 6])
 
    # 反転
    ll.reverse()
    print(ll)  # SinglyLinkedList([6 -> 5 -> 4 -> 3 -> 2 -> 1])
 
    # イテレーション
    for val in ll:
        print(val, end=" ")  # 6 5 4 3 2 1
    print()

def reverse_iterative(head):
    """連結リストの反転（反復版）: O(n) 時間, O(1) 空間
 
    3つのポインタ（prev, curr, next_node）を使って
    各ノードの next を前のノードに付け替える。
    """
    prev = None
    curr = head
    while curr:
        next_node = curr.next   # 次のノードを退避
        curr.next = prev        # ポインタを反転
        prev = curr             # prev を進める
        curr = next_node        # curr を進める
    return prev  # 新しい先頭
 
 
def reverse_recursive(head):
    """連結リストの反転（再帰版）: O(n) 時間, O(n) 空間
 
    再帰でリストの末尾に到達し、戻りながらポインタを反転する。
    コールスタックに O(n) の空間を使う点に注意。
    """
    # ベースケース: 空リストまたは1ノード
    if not head or not head.next:
        return head
    # 再帰: head.next 以降を反転
    new_head = reverse_recursive(head.next)
    # head.next のノードが head を指すようにする
    head.next.next = head
    head.next = None
    return new_head

def has_cycle(head):
    """サイクルの存在判定: O(n) 時間, O(1) 空間
 
    slow（亀）は1ステップずつ、fast（ウサギ）は2ステップずつ進む。
    サイクルがあれば必ず出会い、なければ fast が末尾に到達する。
    """
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False
 
 
def detect_cycle_start(head):
    """サイクルの開始ノードを特定: O(n) 時間, O(1) 空間
 
    Phase 1: slow と fast が出会う地点を見つける
    Phase 2: head と出会い地点から同速度で進め、合流点がサイクル開始
    """
    slow = fast = head
 
    # Phase 1: 出会い地点を見つける
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # サイクルなし
 
    # Phase 2: サイクル開始ノードを特定
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow

def find_middle(head):
    """中間ノードを検出: O(n) 時間, O(1) 空間
 
    slow は1歩、fast は2歩ずつ進む。
    fast がリストの末尾に到達したとき、slow は中間にいる。
    偶数長の場合、2つの中間ノードのうち後者を返す。
    """
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow
 
 
def find_middle_first(head):
    """中間ノードを検出（偶数長の場合は前者を返す）
 
    偶数長のリスト [1, 2, 3, 4] に対して:
    - find_middle は 3 を返す（後者の中間）
    - find_middle_first は 2 を返す（前者の中間）
    """
    slow = fast = head
    while fast and fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    return slow

class DListNode:
    """双方向連結リストのノード"""
    __slots__ = ('val', 'prev', 'next')
 
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next
 
    def __repr__(self):
        return f"DListNode({self.val})"
 
 
class DoublyLinkedList:
    """双方向連結リストの完全実装
 
    番兵ノード（sentinel）を使用して実装を簡潔にする。
    head_sentinel と tail_sentinel は常に存在し、実データは持たない。
 
    構造:
    head_sentinel ⇌ [data1] ⇌ [data2] ⇌ ... ⇌ tail_sentinel
    """
 
    def __init__(self):
        # 番兵ノードの初期化
        self._head = DListNode(0)  # head sentinel
        self._tail = DListNode(0)  # tail sentinel
        self._head.next = self._tail
        self._tail.prev = self._head
        self._size = 0
 
    def __len__(self):
        return self._size
 
    def __iter__(self):
        """前方向イテレータ"""
        curr = self._head.next
        while curr != self._tail:
            yield curr.val
            curr = curr.next
 
    def __reversed__(self):
        """逆方向イテレータ"""
        curr = self._tail.prev
        while curr != self._head:
            yield curr.val
            curr = curr.prev
 
    def __repr__(self):
        values = list(self)
        return f"DoublyLinkedList({values})"
 
    def is_empty(self):
        """空リスト判定: O(1)"""
        return self._size == 0
 
    def _insert_between(self, val, predecessor, successor):
        """2つのノードの間に新しいノードを挿入: O(1)
 
        内部ヘルパーメソッド。全ての挿入操作はこれに帰着する。
        """
        new_node = DListNode(val, predecessor, successor)
        predecessor.next = new_node
        successor.prev = new_node
        self._size += 1
        return new_node
 
    def _remove_node(self, node):
        """指定ノードを削除: O(1)
 
        内部ヘルパーメソッド。全ての削除操作はこれに帰着する。
        番兵ノードは削除しない。
        """
        predecessor = node.prev
        successor = node.next
        predecessor.next = successor
        successor.prev = predecessor
        self._size -= 1
        node.prev = node.next = None  # 参照をクリア
        return node.val
 
    def prepend(self, val):
        """先頭に挿入: O(1)"""
        return self._insert_between(val, self._head, self._head.next)
 
    def append(self, val):
        """末尾に挿入: O(1)
 
        双方向リストでは tail sentinel の prev に挿入するだけ。
        単方向リストの O(n) と比較して大きな改善。
        """
        return self._insert_between(val, self._tail.prev, self._tail)
 
    def insert_at(self, index, val):
        """指定インデックスに挿入: O(min(i, n-i))
 
        先頭と末尾のどちらに近いかに応じて走査方向を選択。
        """
        if index < 0 or index > self._size:
            raise IndexError(f"Index {index} out of range [0, {self._size}]")
 
        # 先頭に近いか末尾に近いかで走査方向を決定
        if index <= self._size // 2:
            curr = self._head.next
            for _ in range(index):
                curr = curr.next
            self._insert_between(val, curr.prev, curr)
        else:
            curr = self._tail.prev
            for _ in range(self._size - index - 1):
                curr = curr.prev
            self._insert_between(val, curr, curr.next)
 
    def pop_front(self):
        """先頭を削除して値を返す: O(1)
 
        Raises:
            IndexError: リストが空の場合
        """
        if self.is_empty():
            raise IndexError("pop from empty list")
        return self._remove_node(self._head.next)
 
    def pop_back(self):
        """末尾を削除して値を返す: O(1)
 
        Raises:
            IndexError: リストが空の場合
        """
        if self.is_empty():
            raise IndexError("pop from empty list")
        return self._remove_node(self._tail.prev)
 
    def delete(self, val):
        """指定値の最初の出現を削除: O(n)
 
        Returns:
            bool: 削除に成功した場合 True
        """
        curr = self._head.next
        while curr != self._tail:
            if curr.val == val:
                self._remove_node(curr)
                return True
            curr = curr.next
        return False
 
    def get(self, index):
        """インデックスでアクセス: O(min(i, n-i))
 
        双方向の走査を活用し、先頭と末尾のどちらに近いかで方向を選択。
        単方向リストの O(i) に対し、最悪ケースが O(n/2) に改善。
        """
        if index < 0 or index >= self._size:
            raise IndexError(f"Index {index} out of range [0, {self._size - 1}]")
 
        if index <= self._size // 2:
            curr = self._head.next
            for _ in range(index):
                curr = curr.next
        else:
            curr = self._tail.prev
            for _ in range(self._size - 1 - index):
                curr = curr.prev
        return curr.val
 
    def front(self):
        """先頭の値を参照（削除しない）: O(1)"""
        if self.is_empty():
            raise IndexError("front from empty list")
        return self._head.next.val
 
    def back(self):
        """末尾の値を参照（削除しない）: O(1)"""
        if self.is_empty():
            raise IndexError("back from empty list")
        return self._tail.prev.val
 
    def reverse(self):
        """リストを反転（in-place）: O(n)
 
        全ノードの prev と next を入れ替える。
        """
        curr = self._head
        while curr:
            curr.prev, curr.next = curr.next, curr.prev
            curr = curr.prev  # prev と next が入れ替わったので prev 方向に進む
        # 番兵ノードを入れ替え
        self._head, self._tail = self._tail, self._head
 
    def to_list(self):
        """Python リストに変換: O(n)"""
        return list(self)
 
    @classmethod
    def from_list(cls, values):
        """Python リストから構築: O(n)"""
        dll = cls()
        for val in values:
            dll.append(val)
        return dll
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    dll = DoublyLinkedList.from_list([1, 2, 3, 4, 5])
    print(dll)                     # DoublyLinkedList([1, 2, 3, 4, 5])
    print(f"Length: {len(dll)}")    # Length: 5
 
    # 両端操作
    dll.prepend(0)
    dll.append(6)
    print(dll)                     # DoublyLinkedList([0, 1, 2, 3, 4, 5, 6])
    print(f"Front: {dll.front()}")  # Front: 0
    print(f"Back: {dll.back()}")    # Back: 6
 
    # 両端からの削除
    dll.pop_front()
    dll.pop_back()
    print(dll)  # DoublyLinkedList([1, 2, 3, 4, 5])
 
    # 逆方向走査
    print("Reversed:", list(reversed(dll)))  # Reversed: [5, 4, 3, 2, 1]
 
    # 反転
    dll.reverse()
    print(dll)  # DoublyLinkedList([5, 4, 3, 2, 1])

class CircularLinkedList:
    """単方向循環連結リスト
 
    tail ポインタのみを保持する設計。
    head は tail.next で O(1) アクセス可能。
 
    空リスト: tail = None
    1ノード:  tail → [A] → (自分自身に戻る)
    複数:     tail → [C] → [A] → [B] → [C]（tail に戻る）
 
    tail を保持する理由:
    - head は tail.next で取得可能
    - 末尾への挿入が O(1) で可能（tail の直後に挿入し tail を更新）
    - head のみ保持する場合、末尾挿入に O(n) の走査が必要
    """
 
    def __init__(self):
        self.tail = None
        self._size = 0
 
    def __len__(self):
        return self._size
 
    def __iter__(self):
        if not self.tail:
            return
        curr = self.tail.next  # head から開始
        for _ in range(self._size):
            yield curr.val
            curr = curr.next
 
    def __repr__(self):
        if not self.tail:
            return "CircularLinkedList([])"
        values = list(self)
        return f"CircularLinkedList({values}, circular)"
 
    def is_empty(self):
        """空リスト判定: O(1)"""
        return self.tail is None
 
    def prepend(self, val):
        """先頭に挿入: O(1)"""
        new_node = ListNode(val)
        if not self.tail:
            new_node.next = new_node  # 自分自身を指す
            self.tail = new_node
        else:
            new_node.next = self.tail.next  # 新ノード → 旧 head
            self.tail.next = new_node       # tail → 新ノード（新 head）
        self._size += 1
 
    def append(self, val):
        """末尾に挿入: O(1)
 
        tail の直後に挿入して tail を更新する。
        """
        self.prepend(val)       # 先頭に挿入
        self.tail = self.tail.next  # tail を新ノードに移動 → 実質的に末尾挿入
        self._size += 0  # prepend で既にインクリメント済み
 
    def pop_front(self):
        """先頭を削除して値を返す: O(1)
 
        Raises:
            IndexError: リストが空の場合
        """
        if self.is_empty():
            raise IndexError("pop from empty circular list")
        head = self.tail.next
        val = head.val
        if self.tail == head:
            # ノードが1つだけ
            self.tail = None
        else:
            self.tail.next = head.next
        self._size -= 1
        return val
 
    def rotate(self, k=1):
        """リストを k 回転（先頭が末尾に移動）: O(k)
 
        ラウンドロビンスケジューリングの次のプロセスへの移動に相当。
        """
        if self.is_empty() or k == 0:
            return
        for _ in range(k % self._size):
            self.tail = self.tail.next
 
    def search(self, val):
        """値の検索: O(n)
 
        Returns:
            bool: 値が見つかった場合 True
        """
        if self.is_empty():
            return False
        curr = self.tail.next
        for _ in range(self._size):
            if curr.val == val:
                return True
            curr = curr.next
        return False
 
    def josephus(self, step):
        """ジョセフス問題を解く
 
        Args:
            step: 除外する間隔（m 番目を除外）
 
        Returns:
            list: 除外された順序のリスト
        """
        if self.is_empty():
            return []
 
        elimination_order = []
        curr = self.tail
        remaining = self._size
 
        while remaining > 0:
            # step - 1 回進む（step 番目のノードの直前に移動）
            for _ in range(step - 1):
                curr = curr.next
            # curr.next を除外
            eliminated = curr.next
            elimination_order.append(eliminated.val)
            if curr == eliminated:
                # 最後の1人
                curr = None
            else:
                curr.next = eliminated.next
            remaining -= 1
 
        self.tail = None
        self._size = 0
        return elimination_order
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    # 基本操作
    cl = CircularLinkedList()
    for i in range(1, 6):
        cl.append(i)
    print(cl)  # CircularLinkedList([1, 2, 3, 4, 5], circular)
 
    # 回転
    cl.rotate(2)
    print(cl)  # CircularLinkedList([3, 4, 5, 1, 2], circular)
 
    # ジョセフス問題: 7人が円形に並び、3番目ごとに除外
    josephus = CircularLinkedList()
    for i in range(1, 8):
        josephus.append(i)
    order = josephus.josephus(3)
    print(f"Josephus elimination order: {order}")
    # [3, 6, 2, 7, 5, 1, 4]

def merge_sorted_lists(l1, l2):
    """2つのソート済み連結リストをマージ: O(n + m) 時間, O(1) 空間
 
    ダミーヘッドを使って簡潔に実装する。
    新しいノードは作成せず、既存のノードをつなぎ替える。
 
    Args:
        l1: ソート済みリストの head
        l2: ソート済みリストの head
 
    Returns:
        マージ後のリストの head
    """
    dummy = ListNode(0)
    curr = dummy
 
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
 
    # 残りをそのまま接続
    curr.next = l1 if l1 else l2
    return dummy.next

def sort_linked_list(head):
    """連結リストのマージソート: O(n log n) 時間, O(log n) 空間
 
    1. リストの中間点で2分割
    2. 各半分を再帰的にソート
    3. ソート済みの2リストをマージ
 
    空間計算量の O(log n) は再帰スタックの深さ。
    配列のマージソートと異なり、追加の配列は不要。
    """
    # ベースケース: 0ノードまたは1ノード
    if not head or not head.next:
        return head
 
    # 中間点で分割
    mid = find_middle_first(head)  # 前者の中間を取得
    second_half = mid.next
    mid.next = None  # リストを切断
 
    # 再帰的にソート
    left = sort_linked_list(head)
    right = sort_linked_list(second_half)
 
    # マージ
    return merge_sorted_lists(left, right)
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    # ソートのテスト
    def build_list(values):
        dummy = ListNode(0)
        curr = dummy
        for v in values:
            curr.next = ListNode(v)
            curr = curr.next
        return dummy.next
 
    def print_list(head):
        values = []
        while head:
            values.append(str(head.val))
            head = head.next
        print(" -> ".join(values))
 
    unsorted = build_list([4, 2, 1, 3, 5])
    print("Before sort:", end=" ")
    print_list(unsorted)  # 4 -> 2 -> 1 -> 3 -> 5
 
    sorted_head = sort_linked_list(unsorted)
    print("After sort: ", end=" ")
    print_list(sorted_head)  # 1 -> 2 -> 3 -> 4 -> 5

def is_palindrome(head):
    """連結リストの回文判定: O(n) 時間, O(1) 空間
 
    1. Fast/Slow ポインタで中間点を見つける
    2. 後半を反転する
    3. 前半と後半を比較する
    4. 後半を元に戻す（リストを破壊しない）
    """
    if not head or not head.next:
        return True
 
    # Step 1: 中間点を見つける
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
 
    # Step 2: 後半を反転
    second_half = reverse_iterative(slow.next)
 
    # Step 3: 比較
    first_half = head
    second_half_copy = second_half  # 後で元に戻すために保存
    is_palin = True
 
    while second_half:
        if first_half.val != second_half.val:
            is_palin = False
            break
        first_half = first_half.next
        second_half = second_half.next
 
    # Step 4: 後半を元に戻す
    slow.next = reverse_iterative(second_half_copy)
 
    return is_palin

def find_intersection(headA, headB):
    """2つのリストの交点を検出: O(n + m) 時間, O(1) 空間
 
    ポインタ A と B を使う。A がリスト A の末尾に達したら
    リスト B の先頭に移動し、B も同様にする。
    両方のポインタは同じ合計距離を進むため、交点で出会う。
 
    交差がない場合、両方とも None に到達して終了する。
    """
    if not headA or not headB:
        return None
 
    a, b = headA, headB
 
    # 両方のポインタが出会うか、両方 None になるまで
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
 
    return a  # 交点ノード、または None（交差なし）

class LRUCache:
    """LRU キャッシュ: 双方向連結リスト + ハッシュマップ
 
    全操作（get, put）が O(1) で動作する。
 
    Attributes:
        capacity: キャッシュの最大容量
        cache: key から DListNode へのマッピング
        _head: 番兵ノード（最新側）
        _tail: 番兵ノード（最古側）
    """
 
    class _Node:
        __slots__ = ('key', 'val', 'prev', 'next')
 
        def __init__(self, key=0, val=0):
            self.key = key
            self.val = val
            self.prev = None
            self.next = None
 
    def __init__(self, capacity):
        """
        Args:
            capacity: キャッシュの最大容量（1以上）
 
        Raises:
            ValueError: capacity が1未満の場合
        """
        if capacity < 1:
            raise ValueError("Capacity must be at least 1")
        self.capacity = capacity
        self.cache = {}  # key -> Node
 
        # 番兵ノード
        self._head = self._Node()
        self._tail = self._Node()
        self._head.next = self._tail
        self._tail.prev = self._head
 
    def _remove(self, node):
        """ノードをリストから除去: O(1)"""
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def _add_to_front(self, node):
        """ノードをリスト先頭（head の直後）に追加: O(1)"""
        node.next = self._head.next
        node.prev = self._head
        self._head.next.prev = node
        self._head.next = node
 
    def _move_to_front(self, node):
        """ノードをリスト先頭に移動: O(1)"""
        self._remove(node)
        self._add_to_front(node)
 
    def get(self, key):
        """キーに対応する値を取得: O(1)
 
        見つかった場合、そのエントリを「最近使用」として先頭に移動する。
 
        Args:
            key: 検索キー
 
        Returns:
            値。キーが存在しない場合は -1
        """
        if key in self.cache:
            node = self.cache[key]
            self._move_to_front(node)
            return node.val
        return -1
 
    def put(self, key, value):
        """キーと値のペアを挿入/更新: O(1)
 
        既存のキーの場合は値を更新し先頭に移動。
        新しいキーの場合は先頭に挿入し、容量超過なら最古を削除。
 
        Args:
            key: キー
            value: 値
        """
        if key in self.cache:
            # 既存のキー: 値を更新して先頭に移動
            node = self.cache[key]
            node.val = value
            self._move_to_front(node)
        else:
            # 新しいキー
            if len(self.cache) >= self.capacity:
                # 容量超過: 最古のエントリ（tail の直前）を削除
                lru_node = self._tail.prev
                self._remove(lru_node)
                del self.cache[lru_node.key]
 
            # 新しいノードを先頭に追加
            new_node = self._Node(key, value)
            self.cache[key] = new_node
            self._add_to_front(new_node)
 
    def __repr__(self):
        items = []
        node = self._head.next
        while node != self._tail:
            items.append(f"{node.key}:{node.val}")
            node = node.next
        return f"LRUCache({' -> '.join(items)}, cap={self.capacity})"
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    lru = LRUCache(3)
 
    lru.put("a", 1)
    lru.put("b", 2)
    lru.put("c", 3)
    print(lru)  # LRUCache(c:3 -> b:2 -> a:1, cap=3)
 
    # "a" にアクセス → 先頭に移動
    print(lru.get("a"))  # 1
    print(lru)  # LRUCache(a:1 -> c:3 -> b:2, cap=3)
 
    # 新しいキー "d" を追加 → 最古の "b" が削除される
    lru.put("d", 4)
    print(lru)  # LRUCache(d:4 -> a:1 -> c:3, cap=3)
 
    # 削除された "b" にアクセス → -1
    print(lru.get("b"))  # -1

class TermNode:
    """多項式の項を表すノード"""
    __slots__ = ('coef', 'exp', 'next')
 
    def __init__(self, coef, exp, next=None):
        self.coef = coef  # 係数
        self.exp = exp    # 指数
        self.next = next
 
    def __repr__(self):
        if self.exp == 0:
            return f"{self.coef}"
        elif self.exp == 1:
            return f"{self.coef}x"
        else:
            return f"{self.coef}x^{self.exp}"
 
 
class Polynomial:
    """多項式クラス（連結リストで実装）
 
    各項は指数の降順でソートされている。
    例: 3x^3 + 2x^2 + 5x + 1
        → [3,3] → [2,2] → [5,1] → [1,0] → None
    """
 
    def __init__(self):
        self.head = None
 
    def add_term(self, coef, exp):
        """項を追加（指数の降順を維持）"""
        if coef == 0:
            return
 
        new_node = TermNode(coef, exp)
 
        # 空リストまたは先頭に挿入
        if not self.head or self.head.exp < exp:
            new_node.next = self.head
            self.head = new_node
            return
 
        # 同じ指数の項が存在する場合は係数を加算
        if self.head.exp == exp:
            self.head.coef += coef
            if self.head.coef == 0:
                self.head = self.head.next
            return
 
        # 挿入位置を探索
        curr = self.head
        while curr.next and curr.next.exp > exp:
            curr = curr.next
 
        if curr.next and curr.next.exp == exp:
            curr.next.coef += coef
            if curr.next.coef == 0:
                curr.next = curr.next.next
        else:
            new_node.next = curr.next
            curr.next = new_node
 
    def __add__(self, other):
        """多項式の加算: O(n + m)"""
        result = Polynomial()
        p1, p2 = self.head, other.head
 
        while p1 and p2:
            if p1.exp > p2.exp:
                result.add_term(p1.coef, p1.exp)
                p1 = p1.next
            elif p1.exp < p2.exp:
                result.add_term(p2.coef, p2.exp)
                p2 = p2.next
            else:
                total_coef = p1.coef + p2.coef
                if total_coef != 0:
                    result.add_term(total_coef, p1.exp)
                p1 = p1.next
                p2 = p2.next
 
        while p1:
            result.add_term(p1.coef, p1.exp)
            p1 = p1.next
        while p2:
            result.add_term(p2.coef, p2.exp)
            p2 = p2.next
 
        return result
 
    def evaluate(self, x):
        """多項式に x を代入して評価: O(n)"""
        result = 0
        curr = self.head
        while curr:
            result += curr.coef * (x ** curr.exp)
            curr = curr.next
        return result
 
    def __repr__(self):
        if not self.head:
            return "0"
        terms = []
        curr = self.head
        while curr:
            terms.append(repr(curr))
            curr = curr.next
        return " + ".join(terms)
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    # p1 = 3x^3 + 2x^2 + 5
    p1 = Polynomial()
    p1.add_term(3, 3)
    p1.add_term(2, 2)
    p1.add_term(5, 0)
    print(f"p1 = {p1}")  # p1 = 3x^3 + 2x^2 + 5
 
    # p2 = x^3 + 4x + 2
    p2 = Polynomial()
    p2.add_term(1, 3)
    p2.add_term(4, 1)
    p2.add_term(2, 0)
    print(f"p2 = {p2}")  # p2 = 1x^3 + 4x + 2
 
    # 加算
    p3 = p1 + p2
    print(f"p1 + p2 = {p3}")  # p1 + p2 = 4x^3 + 2x^2 + 4x + 7
 
    # 評価
    print(f"p3(2) = {p3.evaluate(2)}")  # p3(2) = 4*8 + 2*4 + 4*2 + 7 = 55

# ✗ アンチパターン: 末尾追加と走査だけなら配列で十分
class BadLogBuffer:
    """ログバッファとして連結リストを使用（非推奨）"""
    def __init__(self):
        self.head = None
        self.tail = None
 
    def add_log(self, message):
        """ログを末尾に追加"""
        node = ListNode(message)
        if not self.tail:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
 
    def get_all_logs(self):
        """全ログを取得"""
        logs = []
        curr = self.head
        while curr:
            logs.append(curr.val)
            curr = curr.next
        return logs
 
 
# ○ 正しいアプローチ: 配列（リスト）を使用
class GoodLogBuffer:
    """ログバッファとして配列を使用（推奨）"""
    def __init__(self):
        self.logs = []
 
    def add_log(self, message):
        """ログを末尾に追加: O(1) 償却"""
        self.logs.append(message)
 
    def get_all_logs(self):
        """全ログを取得: O(n)、キャッシュ効率良好"""
        return list(self.logs)
 
    def get_log(self, index):
        """特定のログを取得: O(1)"""
        return self.logs[index]

# ✗ アンチパターン: 循環参照によるメモリリーク
class BadNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.parent_list = None  # リストへの逆参照
 
 
class BadLinkedList:
    def __init__(self):
        self.head = None
 
    def append(self, val):
        node = BadNode(val)
        node.parent_list = self  # 循環参照を形成！
        if not self.head:
            self.head = node
        else:
            curr = self.head
            while curr.next:
                curr = curr.next
            curr.next = node
 
    def clear(self):
        """リストをクリア（メモリリークの可能性）"""
        self.head = None
        # ← 各ノードが self（リスト）を参照しているため
        # ← ノード ↔ リスト の循環参照が GC で回収されない可能性
 
 
# ○ 正しいアプローチ: 循環参照を避ける、または明示的にクリア
class GoodLinkedList:
    def __init__(self):
        self.head = None
 
    def clear(self):
        """メモリリークを防ぐクリア"""
        curr = self.head
        while curr:
            next_node = curr.next
            curr.next = None       # 参照をクリア
            curr = next_node
        self.head = None

# ✗ アンチパターン: O(n^2) になるインデックスベースのアクセス
def print_all_bad(linked_list):
    """全要素を表示（非推奨: O(n^2)）"""
    for i in range(len(linked_list)):
        # get(i) は毎回 head から i 回辿る → O(i)
        # 合計: 0 + 1 + 2 + ... + (n-1) = O(n^2)
        print(linked_list.get(i))
 
 
# ○ 正しいアプローチ: イテレータを使用して O(n) で走査
def print_all_good(linked_list):
    """全要素を表示（推奨: O(n)）"""
    for val in linked_list:  # __iter__ で順次走査
        print(val)
 
 
# ○ 正しいアプローチ: ノードポインタを直接使用
def print_all_direct(head):
    """全要素を表示（推奨: O(n)）"""
    curr = head
    while curr:
        print(curr.val)
        curr = curr.next

import threading
 
# ✗ アンチパターン: スレッドセーフでないリスト操作
class UnsafeSharedList:
    def __init__(self):
        self.head = None
 
    def prepend(self, val):
        # スレッドAとBが同時にprependすると:
        # A: new_node.next = self.head  (head = [1])
        # B: new_node.next = self.head  (head = [1])  ← 同じ head を読む
        # A: self.head = new_node_A     (head = [A, 1])
        # B: self.head = new_node_B     (head = [B, 1])  ← A のノードが失われる！
        self.head = ListNode(val, self.head)
 
 
# ○ 正しいアプローチ: ロックで保護
class ThreadSafeList:
    def __init__(self):
        self.head = None
        self._lock = threading.Lock()
 
    def prepend(self, val):
        with self._lock:
            self.head = ListNode(val, self.head)
 
    def pop_front(self):
        with self._lock:
            if not self.head:
                raise IndexError("pop from empty list")
            val = self.head.val
            self.head = self.head.next
            return val

# テストケース
ll = SinglyLinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
assert ll.to_list() == [0, 1, 2, 3]
assert len(ll) == 4
assert ll.search(2) == 2  # index 2
assert ll.search(99) == -1
ll.delete(2)
assert ll.to_list() == [0, 1, 3]

# テストケース
head = build_list([1, 2, 3, 4, 5])
reversed_head = reverse_iterative(head)
assert list_to_array(reversed_head) == [5, 4, 3, 2, 1]
 
head2 = build_list([1, 2, 3, 4, 5])
reversed_head2 = reverse_recursive(head2)
assert list_to_array(reversed_head2) == [5, 4, 3, 2, 1]
 
# エッジケース
assert reverse_iterative(None) is None  # 空リスト
assert reverse_iterative(ListNode(42)).val == 42  # 1要素

# テストケース
head = build_list([1, 2, 3, 4, 5])
# 末尾から2番目（=4）を削除
new_head = remove_nth_from_end(head, 2)
assert list_to_array(new_head) == [1, 2, 3, 5]
 
# エッジケース: 先頭を削除
head2 = build_list([1, 2])
new_head2 = remove_nth_from_end(head2, 2)
assert list_to_array(new_head2) == [2]

# テストケース
l1 = build_list([1, 3, 5, 7])
l2 = build_list([2, 4, 6, 8])
merged = merge_sorted(l1, l2)
assert list_to_array(merged) == [1, 2, 3, 4, 5, 6, 7, 8]
 
# エッジケース
l3 = build_list([1, 2, 3])
merged2 = merge_sorted(l3, None)
assert list_to_array(merged2) == [1, 2, 3]

# テストケース
# 1 → 2 → 3 → 4 → 5 → 3（サイクル）
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(4):
    nodes[i].next = nodes[i + 1]
nodes[4].next = nodes[2]  # 5 → 3 でサイクル
 
assert has_cycle(nodes[0]) is True
assert find_cycle_start(nodes[0]).val == 3
 
# サイクルなし
normal = build_list([1, 2, 3])
assert has_cycle(normal) is False
assert find_cycle_start(normal) is None

# テストケース
assert is_palindrome(build_list([1, 2, 3, 2, 1])) is True
assert is_palindrome(build_list([1, 2, 2, 1])) is True
assert is_palindrome(build_list([1, 2, 3])) is False
assert is_palindrome(build_list([1])) is True
assert is_palindrome(None) is True

# テストケース
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
assert cache.get(1) == 1       # 1 にアクセス（最近使用に）
cache.put(3, 3)                 # 容量超過 → 2 が削除される
assert cache.get(2) == -1       # 2 は削除済み
cache.put(4, 4)                 # 容量超過 → 1 が削除される
assert cache.get(1) == -1       # 1 は削除済み
assert cache.get(3) == 3
assert cache.get(4) == 4

# テストケース
lists = [
    build_list([1, 4, 7]),
    build_list([2, 5, 8]),
    build_list([3, 6, 9]),
]
merged = merge_k_sorted(lists)
assert list_to_array(merged) == [1, 2, 3, 4, 5, 6, 7, 8, 9]

# テストケース
editor = TextEditor()
editor.insert('H')
editor.insert('l')
editor.insert('l')
editor.insert('o')
assert editor.get_text() == "Hllo"
editor.move_left()
editor.move_left()
editor.move_left()
editor.insert('e')
assert editor.get_text() == "Hello"
editor.move_right()
editor.move_right()
editor.move_right()
editor.insert('!')
assert editor.get_text() == "Hello!"

from collections import deque
 
d = deque([1, 2, 3])
d.appendleft(0)  # 先頭に追加: O(1)
d.append(4)      # 末尾に追加: O(1)
d.popleft()      # 先頭から削除: O(1)
d.pop()          # 末尾から削除: O(1)
 
# ただし、中間のインデックスアクセスは O(n)
# d[i] は deque でも O(n)