题目
给你单链表的头指针 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 <= 5001 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？
解题
方法一：递归
思路
首先在 【迭代, 递归】反转链表 - 方法一：递归 的基础上实现反转链表前 N 个节点。
比如说对于下图链表，执行 reverseN(head, 3)：
解决思路和反转整个链表差不多，只要稍加修改即可：
ListNode succ = null; // 后驱节点
// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 记录第 n + 1 个节点
succ = head.next;
return head;
}
// 以 head.next 为起点，需要反转前 n - 1 个节点
ListNode newHead = reverseN(head.next, n - 1);
head.next.next = head;
// 让反转之后的 head 节点和后面的节点连起来
head.next = succ;
return newHead;
}
具体的区别：
- base case 变为
n == 1，反转一个元素，就是它本身，同时要记录后驱节点。 - 之前反转整个链表时直接把
head.next设置为null，因为整个链表反转后原来的head变成了整个链表的最后一个节点。但现在head节点在递归反转之后不一定是最后一个节点了，所以要记录后驱(succ)（第n + 1个节点），反转之后将head连接上。
接下来解决本题，当 left == 1 时，就相当于反转链表开头的 right 个元素，也就是刚才实现的功能：
ListNode reverseBetween(ListNode head, int left, int right) {
// base case
if (left == 1) {
// 相当于反转前 right 个元素
return reverseN(head, right);
}
// ...
}
当 left > 1 时也可以递归到 left == 1 的情况：
class Solution {
// ...
public ListNode reverseBetween(ListNode head, int left, int right) {
// base case
if (left == 1) return reverseN(head, right);
// 前进到反转的起点触发 base case
head.next = reverseBetween(head.next, left - 1, right - 1);
return head;
}
// ...
}
注意：递归的返回的头节点要接回到前面未反转链表的后面，防止链表断掉。
参考：递归魔法：反转单链表
代码
class Solution {
ListNode succ = null;
public ListNode reverseBetween(ListNode head, int left, int right) {
if (left == 1) return reverseN(head, right);
head.next = reverseBetween(head.next, left - 1, right - 1);
return head;
}
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
succ = head.next;
return head;
}
ListNode newHead = reverseN(head.next, n - 1);
head.next.next = head;
head.next = succ;
return newHead;
}
}
不把 succ 维护成全局变量的实现：
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (left == 1) return reverseN(head, right)[0];
head.next = reverseBetween(head.next, left - 1, right - 1);
return head;
}
ListNode[] reverseN(ListNode head, int n) {
if (n == 1) return new ListNode[]{head, head.next};
ListNode[] arr = reverseN(head.next, n - 1);
head.next.next = head;
head.next = arr[1];
return arr;
}
}
class Solution {
pair<ListNode*, ListNode*> reverseN(ListNode* head, int n) {
if (n == 1) return {head, head->next};
auto pr = reverseN(head->next, n - 1);
head->next->next = head;
head->next = pr.second;
return pr;
}
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (left == 1) return reverseN(head, right).first;
head->next = reverseBetween(head->next, left - 1, right - 1);
return head;
}
};
方法二：迭代
思路
反转链表的部分与 【迭代, 递归】反转链表 - 方法二：迭代 完全相同。
先维护一个哨兵节点(dummy)在头节点前面防止头节点被反转时出问题，迭代到链表的第 left-1 个节点，记录下该节点(beforePart)，以便于之后把反转后的链表接回去，然后再往后推一个节点就是需要反转部分的头节点，同时也是反转完成后的尾节点(partTail)，记录下该节点以便于之后把反转后链表的尾节点接上原链表后面。然后就可以把从当前节点开始的 right-left+1 个节点反转了再拼接回去即可。
代码
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(-1, head), curr = dummy;
int n = right - left + 1;
while (left-- > 1) curr = curr.next;
ListNode beforePart = curr, newNext = null, newPrev = null;
curr = curr.next;
ListNode partTail = curr;
for (int i = 0; i < n; ++i) {
newPrev = curr.next;
curr.next = newNext;
newNext = curr;
curr = newPrev;
}
partTail.next = newPrev;
beforePart.next = newNext;
return dummy.next;
}
}
评论区