LeetCode 92. 反转链表 II

思路
将子链表切割下来并记录左节点前一个节点pre和右节点下一个节点sucess
反转子链表后，pre指向反转后的子链表，左节点（此时为子链表的尾节点指向sucess）

/**
 * 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* reverse(ListNode* head) {
        ListNode* res = new ListNode(0);

        while (head) {
            ListNode* temp = head ->next;
            head ->next = res ->next;
            res ->next = head;
            head = temp;
        }

        return res -> next;
    }
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* res = new ListNode(-1);
        res ->next = head;
        ListNode* leftNode;
        ListNode* rightNode;
        ListNode* cur = res;
        ListNode* pre;
        ListNode* success;

        for (int i = 0; i < left - 1; i++) {
            cur = cur ->next;
        }
        pre = cur;
        leftNode = pre ->next;


        for (int i = 0; i < right - left + 1; i ++) {
            cur = cur ->next;
        }
        rightNode = cur;
        success  = rightNode ->next;

        //分割
        ListNode* temp = new ListNode(0);
        temp ->next = leftNode;
        rightNode ->next = nullptr;

        ListNode* mid = reverse(leftNode);

        pre ->next = mid;
        leftNode ->next = success;

        return res ->next;


    }
};