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]

代码

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* hair = new ListNode();
        hair->next = head;
        ListNode* prev = hair;
        ListNode* pRight = hair;

        for(int i=1;i<left;i++) head = head->next;    // 作为pLeft
        for(int i=1;i<left;i++) prev = prev->next;
        for(int i=0;i<right;i++) pRight = pRight->next;

        ListNode* cur = head;
        prev->next = pRight;
        prev = pRight->next;
        while(prev!=pRight){
            ListNode* nex = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nex;
        }
        return hair->next;
        
    }
};