92. 反转链表 II
给你单链表的头指针 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]
提示:
- 链表中节点数目为
n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
解题思路
通过先理解反转第 1n 个节点的问题,进而来求解反转第 leftright 的节点的问题。
那么,反转第 1~n 个节点的问题如何解决?
- 通过临时变量来保存 n 之后的链表节点,这样做的目的是方便第 1~n-1 之间的节点反转后,方便进行拼接,并且 n 之后的链表节点不会丢失
- 在反转后进行拼接时,同” 反转链表 I “的操作方式是一样的(图解过程完全一致,只是 null 变成了 last 保存的部分)
// 反转第1~n个节点
function reverseNth(head: ListNode | null, n: number): ListNode | null {
// 保存n之后的节点的变量
let last = null;
// 1个节点时,仍然需要保存n之后的变量,不然会丢失这些节点
if (n == 1) {
last = head.next;
return head;
}
// 递归调用,缩小问题的规模进而求解
let newHead = reverseNth(head.next, n - 1);
// 进行节点的拼接
head.next.next = head;
head.next = last;
return newHead;
}
// 理解了反转第1~n个节点的问题后,就可以求解该题了
// 以下是(完整过程)
function reverseBetween(
head: ListNode | null,
left: number,
right: number
): ListNode | null {
// 保存节点
let last = null;
// left为1的情况下,其实就相当于1~n的情况
if (left === 1) {
return reverseNth(head, right);
}
// 如果left不为1的情况下(即1~left-1),直接递归调用即可,即缩小问题的规模进而求解
head.next = reverseBetween(head.next, left - 1, right - 1);
return head;
// 反转第1~n个节点
function reverseNth(head: ListNode | null, n: number): ListNode | null {
if (n == 1) {
last = head.next;
return head;
}
let newHead = reverseNth(head.next, n - 1);
head.next.next = head;
head.next = last;
return newHead;
}
}