递归
解题思路
复杂度
-
时间复杂度：
O(N)，n 为链表长度 -
空间复杂度：
O(N)，n 为递归调用堆栈个数
代码实现
var reverseBetween = function (head, left, right) {
let dmg = { next: head };
let leftNode = dmg;
// 1. 先遍历找到 left 前一个节点
for (let i = 0; i < left - 1; i++) {
leftNode = leftNode.next;
}
// 2. 反转 [left, right] 区间内的链表，并连接到原链表中
leftNode.next = reverser(leftNode.next, right - left + 1);
return dmg.next;
};
var reverser = function (head, n) {
if (n === 1 || !head || !head.next) {
return head;
}
const prev = reverser(head.next, --n);
let tail = head.next;
head.next = head.next.next; // 更新每个 head 指向 tail 尾结点
tail.next = head; // 反转
return prev;
}
迭代
解题思路
新建一个 dmg 哨兵节点指向 head ，反转之后直接返回 dmg.next 即可；
先遍历找到 leftNode 节点，然后反转 [left, right] 区间内的节点；
最后将反转后的链表重新连接起来（画图一眼就能看出来）
复杂度
-
时间复杂度：
O(n)，其中 n 为链表节点个数 -
空间复杂度：
O(1)，仅用到若干额外变量
代码实现
var reverseBetween = function (head, left, right) {
let dmg = new ListNode(0, head);
let leftNode = dmg;
// 1. 先遍历找到 left 前一个节点
for (let i = 0; i < left - 1; i++) {
leftNode = leftNode.next;
}
// 2. 反转 [left, right] 区间内的链表
let prev = null, curr = leftNode.next, next = null;
for (let i = 0; i < right - left + 1; i++) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// 3. 将反转后的链表连接到原链表中
leftNode.next.next = curr;
leftNode.next = prev;
return dmg.next;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 206. 反转链表
上一篇
评论
