/**
 * 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) {
        vector<ListNode*> temp;
        ListNode* p = head;
        for (int i = 1; i < left; i++)
            p = p->next;
        for (int i = left; i < (1 + left + right) / 2; i++, p = p->next)
            temp.push_back(p);
        int len = temp.size() - 1;
        int i;
        if (!((right - left) % 2)) i = (left + right) / 2 + 1, p = p->next;
        else i = (left + right) / 2;
        for ( ; len >= 0; i++, p = p->next, len--)
            swap(temp[len]->val, p->val);
        return head;
    }
};