25. Reverse Nodes in k-Group
25. Reverse Nodes in k-Group
题目
Given the head
of a linked list, reverse the nodes of the list k
at a time, and return the modified list.
k
is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k
then left-out nodes, in the end, should remain as it is.
You may not alter the values in the list's nodes, only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Example 2:
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
Constraints:
- The number of nodes in the list is
n
. 1 <= k <= n <= 5000
0 <= Node.val <= 1000
Follow-up: Can you solve the problem in O(1)
extra memory space?
题目大意
按照每 K 个元素翻转的方式翻转链表。如果不满足 K 个元素的就不翻转。
解题思路
这一题是 第 24 题 的加强版,第 24 题是两两相邻的元素,翻转链表。而本题要求的是 k 个相邻的元素,翻转链表,第 24 题相当于是 k = 2 的特殊情况。
代码
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function (head, k) {
let node = head;
// 将 node 指向第 k + 1 个节点
for (let i = 0; i < k; i++) {
// 若不足 k 个节点,直接返回 head
if (!node) {
return head;
}
node = node.next;
}
// 翻转 1 ~ k 之间的节点
let newHead = reverse(head, node);
// 递归,继续反转后面的节点
head.next = reverseKGroup(node, k);
return newHead;
};
// 反转的 first ~ last - 1 之间的节点
/**
* @param {ListNode} first
* @param {ListNode} last
* @return {ListNode}
*/
var reverse = function (first, last) {
let res = new ListNode(0, first);
while (first.next != last) {
let temp = first.next;
first.next = temp.next;
temp.next = res.next;
res.next = temp;
}
return res.next;
};
相关题目
- [24. 两两交换链表中的节点](./0024.md)
- [1721. 交换链表中的节点](https://leetcode.com/problems/swapping-nodes-in-a-linked-list)
- [2074. 反转偶数长度组的节点](https://leetcode.com/problems/reverse-nodes-in-even-length-groups)