01. Reverse Nodes in k-Group

Difficulty:HardPattern:Linked List In-Place ReversalTime:O(n)Space:O(1)

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. If the number of nodes is not a multiple of k, left-out nodes at the end remain as they are.

How It Works & Algorithmic Design

Solves using Iterative Group Traversal with Pointer Reversal:

Lookahead Check: Verify if at least k nodes exist from current head. If fewer, keep them intact.
Group Reversal: Reverse k nodes in place by adjusting next pointers.
Pointer Rewiring: Connect previous group's tail to the new head of the reversed group, and connect new tail to the next remaining group.

Why This Approach Works Best

Reverses complete groups in linear $O(n)$ time using $O(1)$ extra space.

Example Walkthrough

Input: head = [1,2,3,4,5], k = 2

Reverse in pairs of 2.

Reversal Steps: Group 1: [1,2] -> [2,1]. Group 2: [3,4] -> [4,3]. Last group: [5] (unchanged).

Grouped node reversal.

Output: [2, 1, 4, 3, 5]

Modified list.

Answer: Reverse Nodes in k-Group implementation

function reverseKGroup(head, k) {
  const dummy = { val: 0, next: head };
  let groupPrev = dummy;
  while (true) {
    let kth = groupPrev;
    for (let i = 0; i < k && kth; i++) kth = kth.next;
    if (!kth) break;
    let groupNext = kth.next;
    let prev = groupNext, curr = groupPrev.next;
    while (curr !== groupNext) {
      const tmp = curr.next;
      curr.next = prev;
      prev = curr;
      curr = tmp;
    }
    const tmp = groupPrev.next;
    groupPrev.next = kth;
    groupPrev = tmp;
  }
  return dummy.next;
}

💡 Iterate through linked list in groups of k nodes and reverse pointers in-place.

Key Takeaways

Use lookahead iteration to ensure at least $k$ nodes exist before reversing.
Dummy node simplifies updates to head pointer.
Runs in $O(n)$ time and $O(1)$ extra memory.