给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
示例 1:
输入:head = [1,2,3,4,5], left = 2, right = 4
输出:[1,4,3,2,5]
示例 2:
输入:head = [5], left = 1, right = 1
输出:[5]
第一步:从虚拟结点开始走 m - 1 步,确定 precursor 节点,即需要反转部分的前一个节点
第二步:继续走 n - m + 1,确定 successor 节点,即需要反转部分的后面一个节点
第三步:把 precursor 节点 和 successor 节点中间部分的链表进行反转
第四步:让 precursor 节点的 next 指针指向 中间部分反转后的头节点
第五步:让 中间部分反转后的尾节点的 next 指针指向 successor 节点
public ListNode reverseBetween(ListNode head, int left, int right) {
// 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode precursorNode = dummyNode;
// 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点
for (int i = 0; i < left - 1; i++) {
precursorNode = precursorNode.next;
}
// 第 2 步:从 pre 再走 right - left + 1 步,来到 right 节点
ListNode rightNode = precursorNode;
for (int i = 0; i < right - left + 1; i++) {
rightNode = rightNode.next;
}
// 第 3 步:切断出一个子链表(截取链表)
ListNode leftNode = precursorNode.next;
precursorNode.next = null;
rightNode.next = null;
// 第 4 步:反转截取的链表
reverseList(leftNode);
// 第 5 步:接回到原来的链表中
precursorNode.next = rightNode;
leftNode.next = rightNode.next;
return dummyNode.next;
}
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode();
while (head.next != null) {
ListNode temp = head.next;
temp.next = dummy.next;
dummy.next = temp;
head = head.next;
}
return dummy.next;
}