题目的主要信息：

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

方法一：递归

具体做法：

如果m == 1,就相当于反转链表的前 n 元素； 如果 m != 1我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转，如果把 head.next 的索引视为1，那相对于 head.next，反转的区间应该是从第 m - 1 个元素开始的，以此类推，递归拼接后续已反转的链表；

对于每次反转，如果n等于1，相当于只颠倒第一个节点，如果不是，则进入后续节点（子问题），将后续反转的内容接到前面即可。

class Solution {
public:
    ListNode* temp = NULL;
    ListNode* reverse(ListNode* head, int n){
        if(n == 1){ //只颠倒第一个节点，后续不管
            temp = head->next;
            return head;
        }
        ListNode* node = reverse(head->next, n - 1); //进入子问题
        head->next->next = head; //反转
        head->next = temp; //拼接
        return node;
    }
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m == 1) //从第一个节点开始
            return reverse(head, n);
        ListNode* node = reverseBetween(head->next, m - 1, n - 1); //缩减子问题
        head->next = node; //拼接已翻转
        return head;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，最坏情况下遍历全部链表
• 空间复杂度：$O(n)O(n)$，递归栈深度最坏为$nn$

方法二：头插法迭代

具体做法：

我们可以在链表前加一个表头，后续返回时去掉就好了，使用两个指针，一个指向当前节点，一个指向前序节点，然后遍历到m的位置，后续采用头插法，依次遍历将链表逆序。如下图所示：

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; //当前节点
        for(int i = 1; i < m; i++){ //找到m
            pre = cur;
            cur = cur->next;
        }
        for(int i = m; i < n; i++){ //从m反转到n
            ListNode* temp = cur->next;
            cur->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        return res->next; //返回去掉表头
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，最坏情况下遍历全部链表
• 空间复杂度：$O(1)O(1)$，无额外空间使用