题目：描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
例如：
给出的链表为 1\to 2 \to 3 \to 4 \to 5 \to NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4,
返回 1\to 4\to 3\to 2\to 5\to NULL1→4→3→2→5→NULL.

数据范围： 链表长度 0 < size \le 10000 要求：时间复杂度 O(n)O(n) ，空间复杂度 O(n)O(n)
进阶：时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)
示例1
输入：
{1,2,3,4,5},2,4
复制
返回值：
{1,4,3,2,5}
复制
示例2
输入：
{5},1,1
复制
返回值：
{5}

题解：

1.找到需要反转的的m-n区间的m 前驱节点，兼容m=1的情况，最好新增一个新的链表头部；
2.找到m节点的前驱节点
3.找到n节点
4.获得子链
5.反转子链

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) {
        // write code here
        ListNode tempNode=new ListNode(-1);//
        tempNode.next=head;
        ListNode pre=tempNode;
        //获得m节点的前驱节点
        for(int i=0;i<m-1;i++){
            pre=pre.next;
        }
         //获得n节点
        ListNode right=pre;
        for(int i=m;i<=n;i++){
            right=right.next;
        }
        //son link
        ListNode sonNode=pre.next; //子链
        ListNode rightNode=right.next;//后部链
    
        //链尾置空
        right.next=null;
        pre.next=null;
        
        reverseLinkList(sonNode);
        //子链两端链接-注意反转的顺序
        pre.next=right;
        sonNode.next=rightNode;
        return tempNode.next;
        
    }
    //反转
    public void reverseLinkList(ListNode mid){
        ListNode pre=null;
        ListNode cur=mid;
        while(cur!=null){
           ListNode Cur_node=cur.next;
           cur.next=pre;
           pre=cur;
           cur=Cur_node;
        }  
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58