158 lines
4.1 KiB
JavaScript
158 lines
4.1 KiB
JavaScript
/**
|
||
* Definition for singly-linked list.
|
||
* function ListNode(val, next) {
|
||
* this.val = (val===undefined ? 0 : val)
|
||
* this.next = (next===undefined ? null : next)
|
||
* }
|
||
*/
|
||
/**
|
||
* https://leetcode.cn/problems/reverse-linked-list-ii/?envType=study-plan-v2&envId=top-interview-150
|
||
* @param {ListNode} head
|
||
* @param {number} left
|
||
* @param {number} right
|
||
* @return {ListNode}
|
||
*/
|
||
const reverseBetween = function (head, left, right) {
|
||
|
||
};
|
||
|
||
/*
|
||
思路: 首先找到left指向的节点和right指向的节点，之后把left的前一个节点和right的后一个节点保存起来
|
||
，之后反转left到right的所有节点，再把原先得前后两部分拼接上即可。
|
||
*/
|
||
|
||
function f1(head, left, right) {
|
||
if (left === right) return head; // 无需反转
|
||
let cur = head;
|
||
let i = 1;
|
||
let pre = null;
|
||
let leftNode = null;
|
||
let rightNode = null;
|
||
let next = null;
|
||
while (cur) {
|
||
if (i === left - 1) { // 寻找left的前一个节点
|
||
pre = cur;
|
||
} else if (i === left) { // 寻找left节点
|
||
leftNode = cur;
|
||
} else if (i === right) { // 寻找right 节点
|
||
rightNode = cur;
|
||
next = cur.next;
|
||
rightNode.next = null; // 将链表截断
|
||
break; // 退出循环
|
||
}
|
||
cur = cur.next;
|
||
i++;
|
||
}
|
||
|
||
// 从left到right开始反转
|
||
const rHead = reverseLink(leftNode); // rHead和RightNode指向了同一个节点
|
||
if (pre) {
|
||
pre.next = rHead;
|
||
} else {
|
||
head = rightNode;
|
||
}
|
||
leftNode.next = next;
|
||
return head;
|
||
}
|
||
|
||
/*
|
||
反转一个链表，使用递归
|
||
*/
|
||
function reverseLink(head) {
|
||
// 基本情况：如果链表为空或只有一个节点，直接返回
|
||
if (!head || !head.next) return head;
|
||
|
||
// 递归反转后续链表
|
||
const rHead = reverseLink(head.next);
|
||
|
||
// 当前节点的下一个节点的 next 指向当前节点，反转链表
|
||
head.next.next = head;
|
||
|
||
// 断开当前节点与下一个节点的连接，防止形成环
|
||
head.next = null;
|
||
|
||
return rHead;
|
||
}
|
||
|
||
/*
|
||
反转一个链表使用迭代
|
||
*/
|
||
const reverseLinkedList = (head) => {
|
||
let pre = null;
|
||
let cur = head;
|
||
|
||
while (cur) {
|
||
const next = cur.next;
|
||
cur.next = pre;
|
||
pre = cur;
|
||
cur = next;
|
||
}
|
||
};
|
||
|
||
function ListNode(val, next) {
|
||
this.val = (val === undefined ? 0 : val);
|
||
this.next = (next === undefined ? null : next);
|
||
}
|
||
|
||
/*
|
||
优化：思路和上面是一样的，利用哑节点来优化，减少边界判断情况
|
||
*/
|
||
function f2(head, left, right) {
|
||
// left在等于1时和大于1时处理方式不同，利用哑节点来减少判断情况
|
||
const dummyHead = new ListNode(-1);
|
||
dummyHead.next = head;
|
||
|
||
// 1.寻找left节点的前一个节点pre
|
||
// 这里直接使用for循环，从dummyHead的位置走left-1步即可
|
||
let pre = dummyHead;
|
||
for (let i = 0; i < left - 1; i++) {
|
||
pre = pre.next;
|
||
}
|
||
|
||
// 2.从pre的位置往后走 right - Left + 1步，即可找到right指向的节点
|
||
let rightNode = pre;
|
||
for (let i = 0; i < right - left + 1; i++) {
|
||
rightNode = rightNode.next;
|
||
}
|
||
|
||
// 3.将链表从left到right的位置切断
|
||
const leftNode = pre.next;
|
||
const surr = rightNode.next;
|
||
pre.next = null;
|
||
rightNode.next = null;
|
||
|
||
// 4.反转切断的这一部分
|
||
reverseLinkedList(leftNode);
|
||
|
||
// 5.接回原来的链表中
|
||
pre.next = rightNode;
|
||
leftNode.next = surr;
|
||
return dummyHead.next;
|
||
}
|
||
|
||
/*
|
||
直接在链表上面操作，把要反转的区域
|
||
*/
|
||
|
||
function f3(head, left, right) {
|
||
const dummyHead = new ListNode(-1); // 创建一个哑节点，简化边界情况
|
||
dummyHead.next = head; // 哑节点的next指向链表头
|
||
|
||
let pre = dummyHead; // `pre` 用于指向 `left` 前一个节点
|
||
// 寻找 `left` 的前一个节点
|
||
for (let i = 0; i < left - 1; i++) {
|
||
pre = pre.next;
|
||
}
|
||
|
||
const cur = pre.next; // `cur` 指向要反转部分的第一个节点
|
||
// 从 `left` 到 `right` 反转链表部分
|
||
for (let i = 0; i < right - left; i++) {
|
||
const next = cur.next; // `next` 指向当前节点的下一个节点
|
||
cur.next = next.next; // 跳过 `next` 节点
|
||
next.next = pre.next; // 将 `next` 插入到 `cur` 前面
|
||
pre.next = next; // 更新 `pre.next` 为 `next`
|
||
}
|
||
|
||
return dummyHead.next; // 返回反转后的链表
|
||
}
|