Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Reverse Nodes in k-Group

Problem (restated)

Given the head of a singly linked list and an integer k, reverse the list in groups of k nodes and return the new head. A leftover suffix shorter than k stays in the original order. Rewire pointers; do not swap values.

Intuition

LC 24 is this problem with k = 2. For each group: check that k nodes remain; reverse that run using the whole-list reverse template, then stitch the previous group’s tail to the new group head. Stop when a group is incomplete.

Approaches

Dummy + k-group reverse

Unverified

Time O(n)Space O(1)

Idea. dummy→head. From groupPrev, walk k steps to find kth. If missing, leftover stays. Reverse the open interval (groupPrev, groupNext) so kth becomes the group head; then groupPrev becomes the old group head (now the tail).

Walkthrough. 1→2→3→4→5, k=2. First group: dummy→2→1→3→4→5. Second: 1→4→3→5. 5 left over. Result 2→1→4→3→5.

Trade-offs. True O(1) extra space. Count-then-reverse is the usual interview path; do not reverse a short leftover. k = 1 is a no-op; k = n is LC 206.

Solution

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let groupPrev = dummy;

  const kthFrom = (start: ListNode, n: number): ListNode | null => {
    let cur: ListNode | null = start;
    for (let i = 0; i < n; i++) {
      cur = cur.next;
      if (!cur) return null;
    }
    return cur;
  };

  while (true) {
    const kth = kthFrom(groupPrev, k);
    if (!kth) break;
    const groupNext = kth.next;
    let prev: ListNode | null = groupNext;
    let cur: ListNode | null = groupPrev.next;
    while (cur !== groupNext) {
      const nxt = cur!.next;
      cur!.next = prev;
      prev = cur;
      cur = nxt;
    }
    const newGroupTail = groupPrev.next!;
    groupPrev.next = kth;
    groupPrev = newGroupTail;
  }
  return dummy.next;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let groupPrev = dummy;

  const kthFrom = (start: ListNode, n: number): ListNode | null => {
    let cur: ListNode | null = start;
    for (let i = 0; i < n; i++) {
      cur = cur.next;
      if (!cur) return null;
    }
    return cur;
  };

  while (true) {
    const kth = kthFrom(groupPrev, k);
    if (!kth) break;
    const groupNext = kth.next;
    let prev: ListNode | null = groupNext;
    let cur: ListNode | null = groupPrev.next;
    while (cur !== groupNext) {
      const nxt = cur!.next;
      cur!.next = prev;
      prev = cur;
      cur = nxt;
    }
    const newGroupTail = groupPrev.next!;
    groupPrev.next = kth;
    groupPrev = newGroupTail;
  }
  return dummy.next;
}

Recursive k-group

Unverified

Time O(n)Space O(n/k) stack

Idea. Count k nodes ahead. If you run out, return head unchanged. Otherwise recurse on the rest, then reverse the current k-block onto that already-reversed suffix.

Walkthrough. Same list, k=2: innermost leftover 5; then reverse 3→4 onto 5, then reverse 1→2 onto 4→3→5.

Trade-offs. The shortest statement of the recurrence, at the cost of O(n/k) stack. Prefer iterative unless asked for recursion.

Solution

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  let node = head;
  for (let i = 0; i < k; i++) {
    if (!node) return head;
    node = node.next;
  }
  let prev = reverseKGroup(node, k);
  let cur = head;
  for (let i = 0; i < k; i++) {
    const nxt = cur!.next;
    cur!.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  let node = head;
  for (let i = 0; i < k; i++) {
    if (!node) return head;
    node = node.next;
  }
  let prev = reverseKGroup(node, k);
  let cur = head;
  for (let i = 0; i < k; i++) {
    const nxt = cur!.next;
    cur!.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

Template connection

Reverse-range applied repeatedly: LC 92 once, LC 24 with k=2, this problem with arbitrary k. Dummy head still owns the changing overall head.

Reflection

If the next group has fewer than k nodes, leave it. Otherwise reverse it, attach it to the dummy, and move to the next group.
k = 1 leaves the list unchanged. k equal to the length reverses the whole list. A remainder that is not a full group stays in order.
The new head of a reversed group is the old tail. The old head becomes the group’s new tail.