/*
 * 演算法 / Algorithm: 頭插法原地反轉 (head-insertion in-place reversal).
 * 用 dummy 節點避免 left==1 的特判；prev 停在區段前一個節點，
 * curr 固定為區段原頭，反覆把 curr 後面的節點插到 prev 之後，共 right-left 次。
 * One pass, O(1) extra space.
 */

// LeetCode 給定的節點定義 / LeetCode's node definition:
// struct ListNode { int val; struct ListNode *next; };

struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    // 建一個虛擬頭節點，val 隨便填 0，next 先接到真正的 head。
    // Create a dummy node so the real head always has a predecessor.
    struct ListNode dummy;              // 直接放在堆疊上，不用 malloc / stack-allocated, no malloc needed
    dummy.next = head;                  // dummy 指向原本的 head / dummy points to the original head

    // prev 會停在「反轉區段前一個節點」。從 dummy 出發走 left-1 步。
    // prev will land on the node just before the segment; start at dummy.
    struct ListNode* prev = &dummy;     // &dummy 取 dummy 的位址 / take the address of dummy
    for (int i = 0; i < left - 1; i++)  // 走 left-1 步 / advance left-1 times
        prev = prev->next;              // 沿著 next 前進一格 / step forward along next

    // curr 是反轉區段的原始頭節點，整個過程它「原地不動」，最後變成尾巴。
    // curr is the segment's original head; it stays put and becomes the tail.
    struct ListNode* curr = prev->next; // prev 後面第一個節點 / first node of the segment

    // 重複 right-left 次頭插 / repeat the head-insertion right-left times.
    for (int i = 0; i < right - left; i++) {
        // moved 是要被搬走的節點，就是 curr 後面那一個。
        // moved is the node we splice to the front — the one right after curr.
        struct ListNode* moved = curr->next;   // 取出待搬節點 / grab the node to move

        // 步驟 1：把 moved 從原位置拆下——curr 直接跳過它接到 moved 的下一個。
        // Step 1: unhook moved — curr skips over it to moved->next.
        curr->next = moved->next;

        // 步驟 2：把 moved 插到 prev 正後方（也就是區段最前面）。
        // Step 2: splice moved right after prev (the front of the segment).
        moved->next = prev->next;              // moved 接到目前的區段頭 / moved points to current segment head
        prev->next = moved;                    // prev 改指向 moved / prev now points to moved
    }

    // dummy.next 就是（可能已更新的）新頭節點 / dummy.next is the new head.
    return dummy.next;
}