// 题目给定的标准 ListNode 定义
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode { next: None, val }
  }
}

impl Solution {
    pub fn reverse_between(head: Option<Box<ListNode>>, left: i32, right: i32) -> Option<Box<ListNode>> {
        // 如果不用反转，或者链表为空，直接原样返回
        if left == right || head.is_none() {
            return head;
        }

        // 1. 哑节点 (Dummy Node) 技巧：应对 left = 1 时头节点被换掉的情况
        let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
        
        // pre 指针：负责走到 left 的前一个节点
        let mut pre = &mut dummy;
        for _ in 1..left {
            // 不断深入，获取可变借用
            pre = &mut pre.as_mut().unwrap().next;
        }

        // 2. 切割：把 pre 后面的所有链表节点全部拿走（夺取所有权）
        // 现在 pre.next 变成了 None。part3 装的是从 left 开始到最后的完整链表
        let mut part3 = pre.as_mut().unwrap().next.take();
        
        // 桌子：用来存放反转后的目标区间
        let mut part2_head = None;

        // 3. 开始发牌：只发 (right - left + 1) 张牌
        for _ in left..=right {
            if let Some(mut node) = part3 {
                // (1) 抽出一张牌后，把手里剩下的牌（node.next）重新放回 part3
                part3 = node.next.take();
                
                // (2) 把抽出来的这张牌，压在桌子（part2_head）的最上面
                node.next = part2_head;
                part2_head = Some(node);
            }
        }
        // 循环结束时：
        // part2_head 是反转好的区间 [right -> ... -> left]
        // part3 是剩下的尾巴 [right+1 -> ... -> end]

        // 4. 缝合第一步：找到 part2_head 的尾巴，把 part3 接上去
        let mut tail = &mut part2_head;
        while tail.is_some() {
            tail = &mut tail.as_mut().unwrap().next;
        }
        *tail = part3; // 尾巴的 next 指向剩下的部分

        // 5. 缝合第二步：把拼接好的中间段，接回最初的 pre 后面
        pre.as_mut().unwrap().next = part2_head;

        // 剥去 dummy node 返回最终的新头节点
        dummy.unwrap().next
    }
}

pub struct Solution;