我做过的code题 BM2：链表内指定区间反转【链表】

将一个节点数为 size 链表m位置到n位置之间的区间反转，要求时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) O(1)。

例如：
给出的链表为 1 → 2 → 3 → 4 → 5 → N U L L , m = 2 , n = 4 1rightarrow 2rightarrow 3rightarrow 4 rightarrow 5rightarrow NULL,m=2,n=4 1→2→3→4→5→NULL,m=2,n=4，
返回 1 → 4 → 3 → 2 → 5 → N U L L 1rightarrow 4 rightarrow 3 rightarrow 2 rightarrow 5rightarrow NULL 1→4→3→2→5→NULL。

数据范围：链表长度 0 < s i z e ≤ 1000 , 0 < m ≤ n ≤ s i z e 0 要求：时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) O(1)

示例一：
输入：{1,2,3,4,5},2,4
返回值：{1,4,3,2,5}
示例二：
输入：{5}，1，1
返回值：{5}

初始链表：

添加表头：

找到第m个节点：

找到第m个节点：

重复下列三个指针调换n-m次


最后返回去掉表头res的链表。

class Solution {
public:
    
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // 加个表头
        ListNode* res = new ListNode(-1);
        res->next = head;
        
        ListNode* pre = res;
        ListNode* cur = head;
        ListNode* nex = nullptr;
        
        //找到m
        for(int i=1; i
            pre = cur;
            cur = cur->next;
        }
        //从m反转到n
        for(int i=m;i
            nex = cur->next;
            cur->next = nex->next;
            nex->next = pre->next;
            pre->next = nex;
        }
        //返回去掉表头
        return res->next;
    }
};