面试必刷TOP101：2、链表内指定区间反转

一、题目

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

例如：

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类
     */
       // 
       //说明：方便理解，以下注释中将用left，right分别代替m,n节点 

    public ListNode reverseBetween (ListNode head, int m, int n) {
             //设置虚拟头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next =head;
        ListNode pre = dummyNode;
        for(int i=0;i<m-1;i++){
            pre = pre.next;
        }

        ListNode cur = pre.next;
        ListNode Cur_next ;
        for(int i=0;i<n-m;i++){
            Cur_next = cur.next;
            cur.next = Cur_next.next;
            Cur_next .next = pre.next;
            pre.next = Cur_next ;
        }
        return dummyNode.next;
    }
}