# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # Dummy node to simplify edge cases
        dummy = ListNode(0, head) # dummy on heap
        left_prev = dummy

        # Move left_prev to the node just before "left"
        for _ in range(left - 1):
            left_prev = left_prev.next

        # Reverse sublist from left to right
        cur = left_prev.next
        prev, nxt = None, None
        for _ in range(right - left + 1):
            nxt = cur.next
            cur.next = prev
            prev, cur = cur, nxt
        
        # Reconnect reversed sublist with the rest
        left_prev.next.next = nxt # connect tail of reversed part to the remaining list
        left_prev.next = prev # connect left_prev to the new head of reversed part
        return dummy.next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // Dummy node to simplify edge cases 
        ListNode dummy(0, head);    //dummy on stack
        ListNode* left_prev = &dummy;

        // Move left_prev to the node just before "left"
        for (int i = 0; i < left - 1; i++) {
            left_prev = left_prev->next;
        }

        // Reverse sublist from left to right
        ListNode* cur = left_prev->next;
        ListNode* prev = nullptr;
        ListNode* nxt = nullptr;
        for (int i = 0; i < right - left + 1; i++) {
            nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }

        // Reconnect reversed sublist with the rest
        left_prev->next->next = nxt; // connect tail of reversed part to the remaining list
        left_prev->next = prev;      // connect left_prev to the new head of reversed part
        return dummy.next; // Stack memory is auto cleaned up when function exits
    }
};