描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 𝑂(𝑛)O(n)，空间复杂度 𝑂(1)O(1)。
例如：
给出的链表为 1→2→3→4→5→𝑁𝑈𝐿𝐿 ,m=2,n=4,
返回 1→4→3→2→5→𝑁𝑈𝐿𝐿.
数据范围： 链表长度 0<𝑠𝑖𝑧𝑒≤10000，0<𝑚≤𝑛≤𝑠𝑖𝑧𝑒，链表中每个节点的值满足 ∣𝑣𝑎𝑙∣≤1000
要求：时间复杂度 𝑂(𝑛)O(n) ，空间复杂度 𝑂(𝑛)O(n)
进阶：时间复杂度 𝑂(𝑛)O(n)，空间复杂度 𝑂(1)O(1)
示例1
输入：
{1,2,3,4,5},2,4
返回值：
{1,4,3,2,5}
示例2
输入：
{5},1,1
返回值：
{5}
思路：
这道题的关键是：
①找到“需要转换的序列”前面“最后一个无需转换的节点位置”；
②找到“需要转换的序列”的“第一个节点”；
③找到“需要转换的序列”后“第一个无需转换的节点”。
代码
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
ListNode* reverseBetween(ListNode* head, int m, int n) {
// write code here
ListNode *cur = head, *tmp, *first = head;
ListNode* nhead=new ListNode(-1);//哑节点（虚拟头节点），为了防止m=n=1时，tmp取不到最后一位不需要逆序的节点，而取到了和cur一样的第一位需要逆序的节点
nhead ->next = head;
tmp = nhead;
for(int i = 1; i<m; i++)
{
tmp = cur;//tmp取到需要逆序的前一位
cur = cur->next;//cur取到需要逆序的第一位
}
first = cur;//first用于记住第一位需要逆序的节点，即逆序后的最后一位，用于在最后连接上剩下无需逆序的序列。
for(int i = m; i <=n; i++)//循环需要逆序的序列中的节点，并连接在tmp后（记住：tmp正是无需逆序的最后一个节点）
{
ListNode *next = cur->next;//用于存放剩下的全部节点
cur->next = tmp->next;
tmp->next = cur;
//以上两句是重点，由于无法直接在tmp节点后加节点cur，因此先把cur也连接在tmp的后一个节点，然后将tmp->next指向cur，则成功加入节点cur
cur = next;
}
first->next = cur;//连接上剩下无需逆序的节点
cur = nhead->next;//丢弃哑节点
delete nhead;
return cur;
}
};