模板
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例:
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
思路
解法一：
- 使用虚拟节点
dumpyNode指向head,保证头结点处的插入； - 使用
pre指针指向left处的前一个节点； - 使用
cur指针依次循环right - left次,依次翻转节点，如下图所示。将next指向的节点与cur指向的节点调换顺序； - 返回链表。
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode *dumpyNode = new ListNode(-1, head);
ListNode *pre = dumpyNode;
for (int i = 0; i < left - 1; i++) {
pre = pre->next;
}
ListNode *cur = pre->next;
ListNode *next;
for (int i = 0; i < right - left; i++) {
next = cur->next;
cur->next = next->next; //指向next的next
next->next = pre->next; //指向pre的next
pre->next = next;
}
return dumpyNode->next;
}
};