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

解题思路：链表拆分 + 拼接

​ 我们可以把整个链表看为三段，第一段为指定区间之前的子链表，第二段为要反转的指定区间，第三段为指定区间之后的子链表。

​ 拆分要做的就是将m至n区间子链表从整个链表中分离出来，拼接就是将m~n区间子链表反转后的结果再拼回去。

具体实现：我们需要分别找到m-1、m、n、n+1位置的节点，将m~n区间子链表反转，然后与m-1和n+1节点连接上。

实现代码：

public ListNode reverseBetween(ListNode head, int m, int n){
    if(head.next == null) return head; // 若只有一个节点
    
    // 1.使用虚拟头节点来辅助操作
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    
    // 2.找到m-1位置的节点，用prevNode表示
    ListNode cur = dummy; // 若m是头节点，则m-1就是虚拟头节点
    int i = 0;
    while(i < m - 1){
        cur = cur.next; // 题目保证了m和n是有效的，所以这里不会出现空指针异常
        i++;
    }
    ListNode prevNode = cur; // 此时cur指向的节点即m-1位置节点
    ListNode nodeM = cur.next; // 同时保存m位置节点
    
    // 3. 找到n-1位置的节点，用afterNode表示，由于找到n就相当于找到了n+1，所以这里找n即可
    while(i < n){
        cur = cur.next;
        i++;
    }
    ListNode nodeN = cur; // 此时cur指向的节点即是n位置节点
    ListNode afterNode = cur.next; // cur.next就是n+1位置节点 
    
    // 4. 反转指定m~n区间
    nodeN.next = null; // 先切断n后面的链接，因为在反转函数内部我们以null为结束标志，如果不切断就会导致反转了区间外的节点
    prevNode.next = reverseList(nodeM); // m-1位置的节点拼接上反转后的子链表
    nodeM.next = afterNode; // 反转后的m节点到了末尾，将它与n+1位置节点链接
   
    // 5. 返回真实链表的头节点
    return dummy.next;
}

// 反转函数
private ListNode reverseList(ListNode head){
    ListNode cur = head;
    head = null;
    while(cur != null){
        ListNode curNext = cur.next;
        cur.next = head;
        head = cur;
        cur = curNext;
    }
    return head;
}

​ 时间复杂度O(N)：需要遍历指定区间前的子链表一次、指定区间m~n子链表两次，指定区间后的子链表只需遍历n+1位置上的节点，最坏情况下m是表头，n是表尾，时间复杂度为O(N)。

​ 空间复杂度O(1)：使用几个常量大小的临时变量。