Reverse nodes in k-group

Hard TimeO(n) SpaceO(n/k) stack

Given the head of a linked list and a number k, reverse its nodes in blocks of k and return the new head — [1, 2, 3, 4, 5] with k = 2 becomes [2, 1, 4, 3, 5]. Only complete groups are reversed, so a short final group stays exactly as it is, and every reversed block has to be joined to the one before it.

Examples

Example 1

Input
node = reverseKGroup(buildList([1, 2, 3, 4, 5]), 2)
Output
[2,1,4,3,5]
1, 2 becomes 2, 1 and 3, 4 becomes 4, 3; the lone 5 is short of a group and stays.

Example 2

Input
node = reverseKGroup(buildList([1, 2, 3, 4, 5]), 3)
Output
[3,2,1,4,5]
1, 2, 3 becomes 3, 2, 1, and 4, 5 is short of 3 so it is left alone.

The Code

function buildList(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) {
    head = { val: values[i], next: head };
  }
  return head;
}
function toArray(node) {
  const out = [];
  while (node) {
    out.push(node.val);
    node = node.next;
  }
  return out;
}
function reverseKGroup(head, k) {
  let node = head;
  for (let i = 0; i < k; i++) {
    if (node === null) return head;
    node = node.next;
  }
  let prev = reverseKGroup(node, k);
  let current = head;
  for (let i = 0; i < k; i++) {
    const nextNode = current.next;
    current.next = prev;
    prev = current;
    current = nextNode;
  }
  return prev;
}
toArray(reverseKGroup(buildList([1, 2, 3, 4, 5]), 2));
Step through toArray(reverseKGroup(buildList([1, 2, 3, 4, 5]), 2)) call by call

More like this

All linked lists examples (9) →