描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度
O
(
n
)，空间复杂度
O
(1)。例如：给出的链表为 1→2→3→4→5→
NULL
,
m
=2,
n
=4,返回 1→4→3→2→5→
NULL
.数据范围： 链表长度 0<
size
≤1000，0<
m
≤
n
≤
size
，链表中每个节点的值满足∣
val
∣≤1000要求：时间复杂度
O
(
n
) ，空间复杂度
O
(
n
)进阶：时间复杂度
O
(
n
)，空间复杂度
O
(1)
思路
反转给定区间的链表，需要首先定位到指定的区间，然后在切断区间前后的节点，然后对指定区间的链表进行反转，反转后在与之前切段的节点连接。
注意：链表的实现Java对象，是一种引用类型，所以在对链表进行操作时，需要考虑引用类型的特殊性，变量通过指针指向对象的地址。
实现
public static ListNode reverseBetween (ListNode head, int m, int n) {
// 如果m=n,直接返回
if(m==n){
return head;
}
// 建立一个虚拟节点，防止m=1时，没有前节点的问题
ListNode weekNode=new ListNode(-1);
weekNode.next=head;
// 需要定位到需要反转的链表区间，而且还需要保存反转区间前后的节点信息
// 定义一个节点，保存反转区间前一个节点的信息
ListNode pre=weekNode;
// pre节点的位置需要根据m来获取,例如m=2,那么pre应该从虚拟节点往后移动一个节点，所以pre的位置需要移动m-1个节点
for (int i = 0; i < m - 1; i++) {
pre=pre.next;
}
// 定义一个左指针指向反转区间的第一个节点
ListNode left=pre.next;
// 定一个右指针指向反转区间的最后一个节点
ListNode right=pre;
// 右指针的位置需要根据m以及n的值来计算移动，移动的个数n-m+1，也就是pre节点开始移动要反转区间的长度
for (int i = 0; i < n - m + 1; i++) {
right=right.next;
}
// 定一个节点，来指向反转区间后面的节点
ListNode last=right.next;
// 现在left，right指针已经标记出要反转的链表，接下来需要断开与前后节点的连接了
pre.next=null;
right.next=null;
// 此时，left指针所指的链表就是要进行反转的链表，进行链表的反转
reverseNode(left);
// 反转过后，right指针指向的节点为反转之后的节点。明白这一点很重要
// 反转之前left指针指向反转链表的头节点，反转之后，头节点就变成right指针指向的节点了，这也是反转的意义
// 连接之前断掉的节点
pre.next=right;
left.next=last;
// 因为weeknode是我们添加的虚拟节点，所以需要返回其next
return weekNode.next;
}
private static void reverseNode(ListNode head){
// 2->3->4
// 需要两个指针，分别指向前后两个节点
// pre代表当前节点的前一个节点，所以初始值为null
ListNode pre=null;
// cur 指向当前第一个节点
ListNode cur=head;
while (cur!=null){
// 获取当前节点的下一个节点
ListNode next=cur.next;
// 当前节点指向前一个节点
cur.next=pre;
// pre 往后移动一个节点
pre=cur;
// cur节点往后移动一个节点
cur=next;
}
}