反转链表II（C++解法）

题目

给你单链表的头指针 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]

C++代码

#include <iostream>
using namespace std;//创建链表结构体
struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}
};/*
* 反转链表问题
* 设置一个虚拟头节点，定义一个cur指针指向待反转区域的第一个节点left，
* 定义一个next指针永远指向cur的下一个节点，
* 定义一个pre指针永远指向待反转区域的第一个节点left的前一个节点，在循环过程中不变
* 迭代每一个需要反转的节点，返回反转后的链表
*/
ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode* dummyNode = new ListNode(-1);dummyNode->next = head;ListNode* pre = dummyNode;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 = pre->next;pre->next = next;}return dummyNode->next;
}int main() {ListNode* n1 = new ListNode(1);ListNode* n2 = new ListNode(2);ListNode* n3 = new ListNode(3);ListNode* n4 = new ListNode(4);ListNode* n5 = new ListNode(5);n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = nullptr;ListNode* head = n1;int left = 2, right = 4;ListNode* ans = reverseBetween(head, left, right);while (ans) {cout << ans->val << " ";ans = ans->next;}return 0;
}

分析

反转链表问题，设置一个虚拟头节点，定义一个 cur 指针指向待反转区域的第一个节点 left，定义一个 next 指针永远指向 cur 的下一个节点，定义一个 pre 指针永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变，迭代每一个需要反转的节点，返回反转后的链表。