92. 反转链表 II
难度:中等
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1 输出：[5]
提示：
-
链表中节点数目为 n
-
1 <= n <= 500
-
-500 <= Node.val <= 500
-
1 <= left <= right <= n
吾有一法，可称之为头插法的变态应用。
法源：遍历区域内的节点，运用头插法的思维，遍历完区域内的节点后，区域内的链表将倒置。
如图：
1.定义三个指针变量：pre指向序号 left 前一个节点， cur指向left对应的节点，next =nullptr;
2.next = cur->next ，将next指向的节点插到区域链表的开头，如图中的第二次图解 cur->next = next->next; next->next = pre->next; pre->next = next; 注意先后顺序不能乱。
3.重复2操作，直至遍历完范围区域.
易错：步骤2链表操作容易想错，不是pre->next->next连接next->next,而是cur->next = next->next
源码：
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int left, int right) {
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *pre = dummy;
for( int i = 0; i < left-1; ++ i ) {
pre = pre->next;
}
ListNode *cur = pre->next,*next=nullptr;
for( int i = 0; i < right - left; ++ i ) {
next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
ListNode *tmp = dummy->next;
delete dummy;
return tmp;
}
};
编程中可能会遇到的问题：
1.头节点的特判问题，利用ｄｕｍｍｙ哑节点解决。
2.第一个for循环中注意ｐｒｅ的位置，确定ｉ的终止条件。
3.第二个 ｆｏｒ 循环中，i的终止条件：因为next从 ｌｅｆｔ 的节点的下一个节点遍历，所以遍历的节点数为（right - left），而不是（right - left+1）。
