代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == n || m <= 0 || m > n)
            return head;
        ListNode newHead = new ListNode(1);
        newHead.next = head;
        ListNode beforeNode = newHead, endNode = head;
        for (int i = 1; i < m; i++)
            beforeNode = beforeNode.next;
        for (int i = 1; i <= n; i++)
            endNode = endNode.next;
        ListNode currentNode = beforeNode.next;
        ListNode afterNode = currentNode.next;
        beforeNode.next = endNode;
        for (int j = m; j <= n; j++) {
            currentNode.next = beforeNode.next;
            beforeNode.next = currentNode;
            currentNode = afterNode;
            if(currentNode == null){
                break;
            }
            afterNode = afterNode.next;
        }
        return newHead.next;
    }
}

做这道题目之前一定要做第一道链表反转的题，做完了那道题，这道题就容易很多

算法分析

整个过程分为三个阶段

• 第一阶段 生成新链表，就是只在原链表前新增一个节点。这步非常简单，不用多说。只是提一下这么做的目的，因为后面需要找到调整位置的前一个节点(也就是m值对应链表节点的前一个节点，即下文的beforeNode)，如果m=1，没有新增一个节点的话，beforeNode就不好定位了。
• 第二阶段 调整链表的结构，这一阶段需要找到好几个位置。首先是调整位置的后一个节点(也就是n值对应链表节点的后一个节点，即下文的endNode)，从endNode到末尾是不用反转的。同时需要找到链表的调整位置currentNode和afterNode，由于endNode之后的节点都是不需要反转的，这里直接将endNode挂到beforeNode之后。
• 第三阶段 循环利用头插法往beforeNode之后插入currentNode节点，这里需要注意，整个调整过程中只有currentNode和afterNode节点是变动的，其他节点都只是找到位置，并不发生变化。

最后一个for循环中使用了if判断currentNode是否为空，目的是处理边界条件，即n=size的情况，此时currentNode=null，如果不跳出循环，afterNode=afterNode.next会越界。

算法性能

• 时间复杂度 整个算法只使用了3个for循环，前两个for循环是为了找节点的位置，后一个for循环是调整，时间复杂度是O(n)。
• 空间复杂度 整个算法只声明了几个ListNode变量，额外空间复杂度是O(1),比题目中规定的要低。