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

代码

 

/*** 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 left, int right) {// 创建一个虚拟节点，用于处理边界情况ListNode *dummy = new ListNode(0);dummy->next = head;ListNode *pre = dummy;// 找到left位置的前一个节点for(int i = 1; i < left; i++) {pre = pre->next;}// `start`是需要反转的第一个节点ListNode *start = pre->next;// `then`是需要反转的节点的下一个节点ListNode *then = start->next;// 进行反转操作，将`start`到`right`位置的节点反转for(int i = 0; i < right - left; i++) {start->next = then->next;then->next = pre->next;pre->next = then;then = start->next;}// 返回新的头节点return dummy->next;}
};