class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode *tmpHead = new ListNode;
        tmpHead -> next = head;
        
        ListNode *pre = tmpHead;
        while(-- left > 0) {
            -- right;
            pre = pre -> next;
            head = head -> next;
        }
        while(-- right > 0) {
            head = head -> next;
        }
        auto nxt = head -> next;
        head -> next = nullptr;    // 指向 nullptr, 让其能够在 reverse 中正常结束
        pre -> next = reverse(pre -> next, nxt);
        auto ret = tmpHead -> next;
        delete tmpHead;
        return ret;
    }

private:
    ListNode *reverse(ListNode *head, ListNode *nxt) {
        ListNode *pre = nxt;
        while(head) {
            auto tmp = head -> next;
            head -> next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }
};