头递归 + 拆分
复杂度：
-
时间复杂度：
O(n)，其中 n 为链表的长度，head 指针会在 O(k/n) 个节点上停留，每次停留需要进行一次 O(k) 的翻转操作； -
空间复杂度：
O(1)，只需要建立常数个变量；
代码实现
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
if (head === null || k === 1) return head;
// 1. 先找到要反转的链表区间 [start, end)
let start = head;
let end = head;
for (let i = 0; i < k; i++) {
if (end == null) return head; // 不足 k 个，不需要反转
end = end.next;
}
// 2. 反转区间 [start, end) 的链表，并返回反转后的头节点
let newHead = reverse(start, end);
// 3. 递归反转后续链表并连接起来
start.next = reverseKGroup(end, k);
return newHead;
};
// 反转链表的前 n 个节点，[start, end)
function reverse(start: ListNode, end: ListNode): ListNode {
let prev = null;
let curr = start;
// 基于反转整个链表，while 终止的条件改成 curr ！== end
while (curr !== end) {
let next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// 返回反转后的头结点
return prev;
}
尾递归 + 栈
复杂度
-
时间复杂度：
O(n)，其中 n 是链表的节点数量，需要对每个节点进行更新指针的操作； -
空间复杂度：
O(n)，其中 n 是链表的节点数量；
实现代码
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
if (k === 1 || head === null || head.next === null) return head;
// 1. 先判断链表是否大于 K 个
let curr = head;
for (let i = 0; i < k; i++) {
if (curr === null) return head; // 不足 k 个，不需要反转
curr = curr.next;
}
// 2. 节点大于 K 个，将 k 个节点 依次入栈，node1、node2、node3...，nodek
let stack = [];
curr = head;
for (let i = 0; i < k; i++) {
stack.push(curr)
curr = curr.next;
}
let first = stack[0];
let last = stack[stack.length - 1];
// 3. 开始下一轮反转
first.next = reverseKGroup(last.next, k);
// 4. 尾递归处理，利用栈对链表进行反转
curr = stack.pop();
while (stack.length) {
curr.next = stack.pop();
curr = curr.next;
}
return last;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 24. 两两交换链表中的节点
上一篇
评论
