/*
 * 演算法 / Algorithm: 頭插法原地反轉 (head-insertion in-place reversal).
 * 與 C 版完全相同的邏輯：dummy 消除邊界、prev 固定在區段前、
 * curr 固定為區段原頭，反覆把 curr 後面的節點頭插到 prev 之後。
 * One pass, O(1) extra space.
 */

// struct ListNode { int val; ListNode *next; ... }; 由 LeetCode 提供 / provided by LeetCode.

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // dummy 虛擬頭節點，避免 left==1 時要特判真正的 head。
        // Dummy node removes the special case when the segment includes the real head.
        ListNode dummy{0, head};        // 用大括號初始化：val=0, next=head / brace-init: val=0, next=head
        ListNode* prev = &dummy;        // prev 之後會停在區段前一個節點 / prev will sit before the segment

        // 走 left-1 步，把 prev 移到反轉區段前面。
        // Walk left-1 steps to position prev before the segment.
        for (int i = 0; i < left - 1; ++i)
            prev = prev->next;          // 前進一格 / step one node forward

        // curr 固定為區段原頭，最終沉為尾巴 / curr is the fixed segment head, becomes the tail.
        ListNode* curr = prev->next;

        // 頭插 right-left 次 / perform head-insertion right-left times.
        for (int i = 0; i < right - left; ++i) {
            ListNode* moved = curr->next;   // 待搬節點 = curr 後面那個 / node to move = the one after curr
            curr->next = moved->next;       // 從鏈上拆下 moved / unhook moved from the chain
            moved->next = prev->next;        // moved 接到目前區段頭 / moved points to current segment head
            prev->next = moved;              // prev 改指向 moved，完成頭插 / prev now points to moved
        }

        // 回傳新頭 / return the (possibly new) head.
        return dummy.next;
    }
};