Coding Interview: Reverse Nodes in k-Group

Prompt and Applicable Context

Given the head head of a singly linked list and a positive integer k, reverse each complete group of k consecutive nodes in place. If fewer than k nodes remain at the end, preserve their original order. Rewire nodes rather than swapping value fields.

For example, 1 → 2 → 3 → 4 → 5 becomes 2 → 1 → 4 → 3 → 5 when k = 2, and becomes 3 → 2 → 1 → 4 → 5 when k = 3. Assume 1 ≤ k ≤ n ≤ 5000, the input is acyclic, and the target is O(n) time with O(1) extra space.

This is suitable for coding interviews across algorithms, backend, infrastructure, and general software engineering roles. The hard part is not basic list reversal. It is proving a complete group exists before mutation, preserving the next group entry, reconnecting both boundaries, and showing that no node is lost or placed in a cycle.

What the Interviewer Evaluates

The first signal is whether the candidate separates boundary discovery, segment reversal, and reconnection. Starting to reverse before knowing that k nodes remain makes an incomplete tail difficult to restore without extra storage. A strong solution performs a read-only lookahead before changing any pointer.

The second signal is clear pointer ownership. groupPrev sits before the current group, kth is the last node of a complete group, groupNext is the entry to the following segment, and the old group head becomes the new tail. At the end of every iteration, the finished prefix must remain reachable and groupPrev.next must be the first unprocessed node.

The third signal is an invariant rather than memorized code. Initializing prev to groupNext makes the old group head point to the suffix when it becomes the tail. Once the reversal finishes, only the previous prefix must be attached to kth; the group-to-suffix connection is already correct.

The fourth signal is complexity discipline. Every node is visited at most once by complete-group lookahead and once by reversal, so the total is O(n), while a fixed number of references gives O(1) extra space. A recursive version has the same time bound but consumes stack space proportional to the number of groups.

Questions to Clarify Before Answering

• What happens to a final group smaller than k? It stays unchanged here. Some variants reverse it, which

produces a different result.

• May node values be swapped? No. Nodes may carry identity, external references, or fields besides the value,

so value swapping is not node reversal.

• What values of k are valid? The prompt guarantees 1 ≤ k ≤ n. A reusable function can still reject a

non-integer or a value below one.

• Can the input contain a cycle? This prompt says no. If cycles are possible, the contract must say whether to

reject or transform them; otherwise lookahead may never finish.

• Must the algorithm be in place? Yes. A stack is simpler when O(k) space is allowed, but misses this target.
• Must node objects be reused? Yes. Building a new list that merely copies values violates the contract.

30-Second Answer Framework

“I will add a dummy node before head and keep groupPrev immediately before the current group. Each iteration walks k steps from groupPrev to find kth. If that fails, I return immediately because the tail has not been modified. After saving groupNext = kth.next, I initialize prev to groupNext and reverse the current group one pointer at a time. That makes the old group head the new tail already pointing to groupNext. I connect groupPrev.next to kth, then move groupPrev to the old group head. Each node is visited once for lookahead and once for reversal, giving O(n) time and O(1) extra space.”

Step-by-Step Deep Dive

Start with a dummy node. The list head changes when the first group is reversed. The dummy node makes attaching the prefix to the new group head identical for the first and every later group, avoiding a special head case.

Each iteration first performs complete-group lookahead. Move exactly k times from groupPrev to obtain kth. If the walk reaches null, fewer than k nodes remain, so return dummy.next. The lookahead has not written any pointer, which is why the incomplete tail remains unchanged automatically.

The implementation is:

class ListNode {
  constructor(value, next = null) {
    this.value = value
    this.next = next
  }
}

function reverseKGroup(head, k) {
  if (!Number.isInteger(k) || k < 1) {
    throw new RangeError('k must be a positive integer')
  }

  const dummy = new ListNode(0, head)
  let groupPrev = dummy

  while (true) {
    let kth = groupPrev

    for (let step = 0; step < k; step += 1) {
      kth = kth.next
      if (kth === null) {
        return dummy.next
      }
    }

    const groupNext = kth.next
    let prev = groupNext
    let current = groupPrev.next

    while (current !== groupNext) {
      const nextNode = current.next
      current.next = prev
      prev = current
      current = nextNode
    }

    const oldGroupHead = groupPrev.next
    groupPrev.next = kth
    groupPrev = oldGroupHead
  }
}

Trace 1 → 2 → 3 → 4 → 5 with k = 3. Lookahead finds kth = 3, and groupNext = 4 is saved. Set prev = 4, then write 1.next = 4, 2.next = 1, and 3.next = 2. Node 3 is now the group head, while node 1 is the tail and already reaches node 4. Attach the dummy node to 3 and move groupPrev to node 1. The next lookahead cannot find three nodes, so it returns without touching 4 → 5.

The loop invariant has three parts. At loop entry, the prefix through groupPrev has been correctly transformed in complete groups; groupPrev.next is the first unprocessed node; and all unprocessed nodes remain reachable in input order. Failed lookahead makes no writes, so the invariant directly proves the incomplete tail is preserved. Successful lookahead limits reversal to exactly k nodes, while groupNext preserves the suffix entry. After reconnection, the finished prefix grows by one group and the invariant is restored. Every successful iteration consumes k new nodes, so the algorithm terminates.

Lookahead and reversal each touch a node at most once across all iterations. The total work is therefore at most about 2n node visits: O(n), not O(nk). The dummy node and pointer count do not grow with input, so auxiliary space is O(1).

If extra space is allowed, pushing one group onto a stack and popping it is easier to write but uses O(k) space. A recursive solution can confirm one complete group, reverse it, and recurse on the suffix, using O(n / k) stack space. The iterative version is the right recommendation for a constant-space target. For a small input where the priority is a quickly reviewable first version, the stack approach can be a reasonable explicitly stated trade-off.

Tests must do more than compare value arrays. Save the set of original node references, traverse the result, and assert that it is acyclic, has the same node count, and contains exactly the same references before checking order. Cover a defensive empty input, one node, k = 1, n = k, an evenly divisible length, an incomplete tail, duplicate values, and the maximum size. Duplicate values are especially useful because value-only tests cannot prove node objects were reused.

High-Quality Sample Answer

“I would first confirm that fewer than k trailing nodes stay in order and that values cannot be swapped. My iterative state is a dummy node plus a fixed number of references. groupPrev always sits immediately before the current group. I walk k steps from it, and if kth does not exist, return before changing any tail pointer.

For a complete group, I save groupNext. I initialize prev to groupNext, then apply the standard three-pointer reversal from the old group head until reaching groupNext. That initialization matters: when the old head becomes the tail, its next already reaches the following segment. After reversal, kth is the new head. I attach groupPrev.next to it and move groupPrev to the old head.

The invariant is that the processed prefix is correct and connected, groupPrev.next is the first unprocessed node, and the suffix remains in input order. A complete reversal grows the prefix; an incomplete group causes no write, preserving the tail. Every node is visited at most once for lookahead and once for reversal, so time is O(n) and extra space is O(1). I would verify node identity and acyclicity, not only the value sequence.”

Common Mistakes

• Reversing before confirming a full group → an incomplete tail is mutated and difficult to restore →

perform read-only lookahead first.

• Starting reversal with prev = null → the group is temporarily detached from the suffix and easily left

disconnected → start with prev = groupNext.

• Connecting only the new group head → the new tail may not reach the suffix → **preserve groupNext and

verify the new tail points to it.**

• Keeping kth as the next predecessor → the next group boundary is wrong → **move groupPrev to the old

group head.**

• Swapping node values → node identity and attached-field semantics are broken → change only next.
• Claiming recursive auxiliary space is O(1) → the call stack grows with group count → **use iteration for

constant extra space.**

• Testing only the value sequence → lost, copied, or cyclic nodes may escape detection → **also verify reference

identity, count, and acyclicity.**

• Multiplying lookahead by reversal into O(nk) → groups are disjoint across iterations → **sum total visits

per node.**

Follow-Up Questions and Responses

Follow-up 1: What if the final group smaller than k must also be reversed?

Failed lookahead can no longer return immediately. It can also count the actual number of remaining nodes and reverse that shorter segment, or the algorithm can compute list length first and use min(k, remaining) as the group size. The termination part of the invariant changes, and a case with n < k becomes mandatory.

Follow-up 2: How would you reverse alternating groups?

Continue to look ahead by complete k-node groups and keep a Boolean flag. A reverse group uses the original logic; a skipped group leaves pointers untouched and advances groupPrev by k nodes. Clarify the incomplete-tail rule again, because whether it counts as a skipped or reversed group changes the result.

Follow-up 3: How can you prove the algorithm creates no cycle?

The local proof uses two boundaries: save groupNext, which is outside the current group, and reverse starting from prev = groupNext until current === groupNext. Every rewritten edge points from the current node to an already processed predecessor or the suffix entry, never back into the still-unprocessed part of the current group. Tests should also run a fast-slow cycle check and assert the traversed node count equals the input count.

Follow-up 4: What changes for a list with one hundred million nodes?

The asymptotic bounds stay the same, but recursion must be avoided, nodes must not be copied, and timeout and cancellation behavior matter for one long operation. If the list resides in external storage or spans machines, random rewiring and atomic visibility dominate the problem. The in-memory algorithm cannot be transferred directly; data layout, transaction boundaries, and recoverable checkpoints must be defined first.