3.3 In-Place Reversal

Demo: Reverse Nodes in k-Group — LC 25 (Hard — Meta High)

Statement (Demo): Given the head of a linked list and an integer k, reverse the nodes k at a time. If fewer than k nodes remain at the end, leave them as they are. Return the new head. Example: head=[1,2,3,4,5], k=2 → [2,1,4,3,5] | ⚡ n ≤ 5000, 1 ≤ k ≤ n

Approach: First count whether k nodes exist — if not, leave that part alone. If they do, solve the rest recursively first, then reverse the current k nodes with the standard reversal and attach them to that result.

function reverseKGroup(head, k) {
  let count = 0,
    node = head;
  while (node && count < k) {
    node = node.next;
    count++;
  }
  if (count < k) return head; // fewer than k left → unchanged
  let prev = reverseKGroup(node, k); // solve the next group first
  let cur = head;
  while (count--) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

Complexity: Time O(n), Space O(n/k) recursion (O(1) iteratively)