翻转链表中第m个节点到第n个节点的部分
注意事项
m，n满足1 ≤ m ≤ n ≤ 链表长度
样例
给出链表1->2->3->4->5->null， m = 2 和n = 4，返回1->4->3->2->5->null
挑战
在原地一次翻转完成
代码
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* }
*/
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (m >= n || head == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
for (int i = 1; i < m; i++) {
if (head == null) {
return null;
}
head = head.next;
}
// premNode 代表第 m-1 个结点
ListNode premNode = head;
// mNode 是第 m 个结点即要翻转的第一个结点，翻转后的最后一个结点
ListNode mNode = head.next;
// 两根指针
ListNode nNode = mNode, postnNode = mNode.next;
// 翻转
for (int i = m; i < n; i++) {
if (postnNode == null) {
return null;
}
ListNode temp = postnNode.next;
postnNode.next = nNode;
nNode = postnNode;
postnNode = temp;
}
// 最后 nNode 指向第 m 个结点，postnNode 指向第 m+1 个结点
// 连接
mNode.next = postnNode;
premNode.next = nNode;
return dummy.next;
}
}
