题解 | #链表内指定区间反转#

public ListNode reverseBetween (ListNode head, int m, int n) {
        //定义返回结果
        ListNode resultHead = head;
        //当m == n时 直接返回首节点
        if(m == n) {
            return head;
        }
        //找到m之前的节点和n之后的节点 以及m和n两个位置的节点
        ListNode mNode = null;
        ListNode nNode = null;
        ListNode preNode = null;
        ListNode tempNode = null;
        ListNode lastNode = null;
        //正常情况  m n 不是首节点和尾节点的情况
        //定义指针变量 用来计数
        int i = 1;
        while(i < n){
            //已经排除m与n相等的情况，可以直接先找到m
            if(i == m){
                //存在一种特殊情况，当m=1 此时preNode直接就是首届点
                //此时可以为mNode赋值
                preNode = tempNode;
                mNode = head;
            }
            //记录上一个节点
            tempNode = head;
            head = head.next;
            i++;
        }
        //循环结束，进入m之前的节点和n出来之后的节点都可以计算出来
        if(head.next != null){
            lastNode = head.next;
            head.next = null;
        }
        //开始反转
        ListNode reverse = ReverseList(mNode);
        //反转结束 确定反转后m和n位置的节点
        if(preNode == null){
            //说明m就是首节点的位置
            resultHead = reverse;
        }else{
            preNode.next = reverse;
        }
        if(lastNode != null){
            while(reverse.next != null){
                reverse = reverse.next;
            }
            //说明n就是首页点的位置，不需要做任何操作
            reverse.next = lastNode;
        }
        return resultHead;
}

public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null){
            //当确保时节点的最后一个节点时作为方法返回值返回
            return head;
        }
        ListNode resultNode = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return resultNode;
}

解题思路：
1、借助在BM1题目中写的翻转链表的方法
2、特殊请款判断 m与n是否相等 如果相等直接返回传入head即可
3、根据0 <= m <= n < size的条件，之前已经排除了m和m相等的情况，只需要得到m和n两个位置的节点即可
4、找到两个位置节点的同时，记录m的上一个节点和n的下一个节点
5、将n位置的下一个节点设置为空，然后将m节点作为参数传入BM1方法中去，得到反转之后的链表
6、在将反转之后的链表首位节点加上即可