NC21：链表内指定区间反转

解法1：双指针法

pre先走m-1步到达位置m的前驱节点，pre不动，然后令cur等于pre->next也就是位置m的起始节点（不变），将[m+1,n]这段链表由前至后的插入到位置m的前面，也就是pre的后面
即：我们每次循环就是将cur的next节点插入到pre的后面，这样插了n-m次后，就完成反转了

  public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        // 设置哑节点的好处：
        //在m=1时，我们也有前驱节点，也可以将cur的next节点依次插入到pre的后面
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        ListNode pre=dummy;
        // 找到m的前驱节点
        for(int i=1;i<m;i++){
            pre=pre.next;
        }
        ListNode cur=pre.next;
        // 每次循环将tmp节点插入到pre的后面
        for(int i=m;i<n;i++){
            ListNode tmp=cur.next;
            cur.next=tmp.next;// cur将tmp节点后面的链表连接起来
            tmp.next=pre.next;// 将tmp插入到pre后面
            pre.next=tmp;
        }
        //例如0->1->2->3->4->5->6->7->8->9->10,翻转2--8；
        // 第1次i=2：0->1->3->2->4->5->6->7->8->9->10
        // 第2次i=3：0->1->4->3->2->5->6->7->8->9->10
        // 第3次i=4：0->1->5->4->3->2->6->7->8->9->10
        // 第4次i=5：0->1->6->5->4->3->2->7->8->9->10
        // 第5次i=6：0->1->7->6->5->4->3->2->8->9->10
        // 第6次i=7：0->1->8->7->6->5->4->3->2->9->10 
        return dummy.next;
    }

解法2：暴力求解

  public ListNode reverseBetween(ListNode head, int m, int n) {
      if(head == null) {
          return head;
      }
        List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            list.add(cur.val); //所有元素放入集合
            cur = cur.next;
        } 
        int i = m - 1; //注意索引要减一，因为集合从0开始
        int j = n - 1;
        while (i < j) { //交换m到n的元素
            int temp = list.get(i);
            list.set(i, list.get(j));
            list.set(j, temp);
            i++;
            j--;
        }
        ListNode dumy = new ListNode(0);
        ListNode res = dumy;
        for (int k = 0; k < list.size(); k++) {
            dumy.next = new ListNode(list.get(k)); //重新串节点
            dumy = dumy.next;
        }
        return res.next;
    }
}