86 lines
2.4 KiB
JavaScript
86 lines
2.4 KiB
JavaScript
/**
|
||
* Definition for singly-linked list.
|
||
* function ListNode(val, next) {
|
||
* this.val = (val===undefined ? 0 : val)
|
||
* this.next = (next===undefined ? null : next)
|
||
* }
|
||
*/
|
||
/**
|
||
* @param {ListNode} head
|
||
* @param {number} k
|
||
* @return {ListNode}
|
||
*/
|
||
const reverseKGroup = function (head, k) {
|
||
|
||
};
|
||
|
||
function ListNode(val, next) {
|
||
this.val = (val === undefined ? 0 : val);
|
||
this.next = (next === undefined ? null : next);
|
||
}
|
||
|
||
/*
|
||
这个问题可以拆解成n个leetcode的子问题，直接利用k把区间划分出来，调用reverseBetween即可
|
||
*/
|
||
function f1(head, k) {
|
||
// 利用哑节点来处理头节点问题
|
||
const dummyHead = new ListNode(-1);
|
||
dummyHead.next = head;
|
||
let left = 2;
|
||
let right = left + k - 1;
|
||
const n = getListLength(dummyHead);
|
||
while (right <= n) {
|
||
reverseBetween(, left, right);
|
||
left = right + 1;
|
||
right = left + k - 1;
|
||
}
|
||
return dummyHead.next;
|
||
}
|
||
|
||
/**
|
||
*
|
||
* @param {*} head 头节点
|
||
* @param {*} left 要反转的区域的第一个节点
|
||
* @param {*} right 要反转的区域的最后一个节点
|
||
* @returns 返回区域反转后的节点
|
||
*/
|
||
const reverseBetween = function (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; // 返回反转后的链表
|
||
};
|
||
|
||
/**
|
||
* 获取链表的节点个数
|
||
* @param {ListNode} head - 链表的头节点
|
||
* @return {number} - 链表的节点个数
|
||
*/
|
||
let getListLength = function (head) {
|
||
let count = 0; // 初始化计数器
|
||
let current = head; // 初始化当前节点为链表头
|
||
|
||
// 遍历整个链表，直到链表末尾
|
||
while (current !== null) {
|
||
count++; // 每遍历一个节点，计数器加一
|
||
current = current.next; // 移动到下一个节点
|
||
}
|
||
|
||
return count; // 返回链表的长度
|
||
};
|