Skip to main content

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.