Reverse Linked List II

アルゴリズム概要

問題説明

単方向連結リストの先頭 head と整数 left, right が与えられる。 位置 left から right までのノードを反転し、結果のリストを返して下さい。

入出力例

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Input: head = [5], left = 1, right = 1
Output: [5]

制約条件

• リスト内のノード数を n とする: 1 ≤ n ≤ 500
• ノードの値: -500 ≤ Node.val ≤ 500
• 位置の範囲: 1 ≤ left ≤ right ≤ n

戦略

• 区間反転: 指定区間 [left, right] を標準の単方向リスト反転で処理
• 原地処理: 追加ノード割当なし（番兵ノード不使用）
• 一回走査: O(n) 時間で完了
• 特殊ケース対応: left==1 の場合は先頭から反転

主要ポイント

時間: O(n) 空間: O(1)

番兵ノードを使わず、left==1 を個別処理することで追加割当をゼロに抑えた最適実装。

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

Python実装

from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    """
    Reverse Linked List II
    - 一回走査・O(1)追加メモリ・番兵ノード不要
    - Time: O(n), Space: O(1)
    """

    def reverseBetween(
        self,
        head: Optional[ListNode],
        left: int,
        right: int
    ) -> Optional[ListNode]:
        # エッジケース: 空リストまたは区間長1
        if head is None or left == right:
            return head

        # Case 1) 先頭から反転（left == 1）
        if left == 1:
            prev: Optional[ListNode] = None
            curr: Optional[ListNode] = head
            # 先頭から right 個を反転
            for _ in range(right):
                next_: Optional[ListNode] = curr.next
                curr.next = prev
                prev = curr
                curr = next_
            # 旧先頭を残りに接続
            head.next = curr
            return prev  # 新しい先頭

        # Case 2) 中間以降の反転（left > 1）
        # 1) left-1 位置まで進めて pre を取得
        pre: ListNode = head
        for _ in range(1, left - 1):
            pre = pre.next

        # 2) 区間 [left, right] を反転
        start: ListNode = pre.next
        prev: Optional[ListNode] = None
        curr: Optional[ListNode] = start
        for _ in range(right - left + 1):
            next_: Optional[ListNode] = curr.next
            curr.next = prev
            prev = curr
            curr = next_

        # 3) 再接続
        pre.next = prev
        start.next = curr
        return head

フローチャート

フローの説明：
1. 空リストまたは区間長1の場合は即座に返す
2. left==1 なら先頭から right 個を反転し、旧先頭を残りに接続
3. left>1 なら pre を left-1 位置まで進める
4. 区間を反転し、pre.next と start.next で再接続
5. 元のリスト先頭を返す

計算量分析

手法比較