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

思路

首先找到第一个开始的反转节点
反转一个链表须要三个半节点：反转链表的第一个（算半个）pre->next，反转链表过程中的第一个head，反转链表过程中未反转部分的第一个nxt，反转链表未反转部分的第二个aft。
每次让nxt的next只想head，之后head变为nxt，这样即实现了一个节点反转到头节点的过程。之后nxt转为未反转部分的第一个，也即原来的aft，aft后移。
全部移动完成后，须要将原来反转链表的第一个pre->next的next设置为nxt，以此实现反转后的尾节点与后续节点链接。之后pre的next节点设置为反转后的第一个节点head。返回第一个节点即可。
为了方便返回第一个节点，这里在头节点前插入新节点。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m==n) return head;
        int cnt = 1;
        ListNode* pre = new ListNode(0);
        pre->next = head;
        ListNode* h = pre;
        while(cnt<m){
            pre=head;
            head=head->next;
            cnt++;
        }
        ListNode* nxt=head->next,*aft=head->next->next,*lst = head;
        while(cnt<n){
            nxt->next = head;
            head=nxt;
            nxt=aft;
            if(aft)aft=aft->next;
            cnt++;
        }
        pre->next->next = nxt;
        pre->next = head;
        return h->next;
    }
};