Reverse Nodes in k-Group
Problem
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
Solution
/**
* 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}
*/
var reverseKGroup = function(head, k) {
const dummy = new ListNode(0, head);
let l = head; // left most node of reverse range
let r = head; // first node after reverse range
let prevGroupTail = dummy; // last node of previous group (ie. node before l)
while (true) {
let count = 0; // number of nodes left
for (; count < k && r; count++) {
r = r?.next;
}
// not enough nodes left to form group
if (count !== k) {
break;
}
// reverse group
let cur = l;
let prev = r;
while (cur !== r) {
[cur.next, cur, prev] = [prev, cur.next, cur];
}
// connect two groups
[prevGroupTail.next, prevGroupTail, l] = [prev, l, r];
}
return dummy.next;
};
We reverse the linked list head
, k
nodes at a time and reconnect the new start of the group to the tail of the previous group. We use l
and r
as the range of nodes to reverse (ie. the nodes in range of [l, r)
forms a k
group). Furthermore, r
is also used as a lookahead to ensure there are still at least k
nodes left to form a complete group, otherwise we terminate.