思路：获取要反转的区间，拆开之后进行反转再拼接
/**
* 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 m, int n) {
// write code here
ListNode* temp = new ListNode(0);
temp->next = head;
ListNode* left = temp;
//left为前段不反转的最后一个节点
for(int i = 0; i<m-1; i++){
left = left->next;
}
ListNode* right = left;
//right为反转区间的最后一个节点
for(int i = 0; i<n-m+1; i++){
right = right->next;
}
//leftNode为反转区间的第一个节点
ListNode *leftNode = left->next;
//RightNode为后段不反转区间的第一个节点
ListNode *RightNode = right->next;
//前段不反转的最后一个节点之后断开
left->next = nullptr;
//后段不反转的第一个节点之前断开
right->next = nullptr;
//对反转区间进行反转之后，leftNode为最后一个节点，right为第一个节点
ReverseList(leftNode);
left->next = right;
leftNode->next = RightNode;
return temp->next;
}
void ReverseList(ListNode* head){
ListNode* ret = nullptr;
ListNode* temp = nullptr;
ListNode* result = head;
while(result){
temp = result->next;
result->next = ret;
ret = result;
result = temp;
}
}
};
