Reverse Nodes in K-Group

1. Problem & Core Objective

Reverse the nodes of the list k at a time and return the modified list. If the number of remaining nodes is fewer than k, leave them as they are.

head = [1,2,3,4,5], k = 2   →   [2,1,4,3,5]
head = [1,2,3,4,5], k = 3   →   [3,2,1,4,5]

You may not alter the values — only the node links.

Constraints: 1 <= k <= n <= 5000 · 0 <= Node.val <= 1000

What's actually being tested: whether you can run a known routine (reversal, from question 1) repeatedly on segments and stitch the pieces back together correctly. The reversal is easy; the stitching is the hard part, and it's where every bug lives.

This is the hardest question in the section.

2. First-Principles Thought Process

The reversal is already solved

Question 1 reverses a whole list. Reversing exactly k nodes is the same loop with a counter:

for (int i = 0; i < k; i++) {
    ListNode next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}

So the algorithm isn't the problem. The problem is everything around it.

What actually goes wrong

Reverse [1,2,3] inside 1 → 2 → 3 → 4 → 5 and you get a fragment 3 → 2 → 1, plus two loose ends:

• The node before the group must now point at 3 (the new first).
• Node 1 (the new last) must now point at 4 (the start of the next group).

Get either wrong and the list fragments or cycles. This bookkeeping is the question.

The check that must come first

"If fewer than k nodes remain, leave them alone" means you have to look ahead k nodes before reversing anything. Reverse first and check later, and you've already corrupted a tail you were supposed to preserve — and reversal isn't cheaply undoable mid-stream.

So each iteration is: count k ahead → if short, stop → otherwise reverse and stitch.

Two useful observations

The group's original first node becomes its last. So before reversing, save groupStart; afterwards it's the tail, and it's what must point at the next group.

A dummy head removes the first-group special case. The first group has no predecessor to rewire — unless a dummy provides one. Fourth appearance of this idiom in the section, same reason every time.

3. Solution Paths

Approach 1 — Copy values into an array, reverse chunks, write back (brute force)

public ListNode reverseKGroup(ListNode head, int k) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode p = head; p != null; p = p.next) vals.add(p.val);

    for (int i = 0; i + k <= vals.size(); i += k)               // only full groups
        Collections.reverse(vals.subList(i, i + k));

    ListNode p = head;
    for (int v : vals) { p.val = v; p = p.next; }               // write values back
    return head;
}

• Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "The problem says you may not alter the values. Doesn't this do exactly that?"

Yes — and that's the fatal objection, not the space. The constraint exists because in a real list the nodes carry payloads, identity, or external references; permuting val fields produces the right sequence while attaching every payload to the wrong node.

It happens to pass LeetCode's tests, since they compare values. It fails the actual requirement.

⭐ "Why i + k <= vals.size() rather than i < vals.size()?"

To skip an incomplete trailing group. With n = 5, k = 2, the loop runs for i = 0 and i = 2 but not i = 4, leaving the last element alone — which is what the problem wants. Using i < size would reverse a 1-element tail, which is harmless here but would be wrong for a partial group of 2 when k = 3.

"Is O(n) space the real problem?"

Not primarily. At n = 5000 an array of integers is nothing. The disqualifier is mutating values instead of links. I'd mention this solution to show I understand the shape, then say plainly why it doesn't satisfy the constraint.

Approach 2 — Recursive, reversing each group (clean, O(n/k) stack)

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode check = head;
    for (int i = 0; i < k; i++) {                  // are there k nodes left?
        if (check == null) return head;            // fewer than k — leave as is
        check = check.next;
    }

    ListNode prev = reverseKGroup(check, k);       // solve the REST first
    ListNode cur = head;
    for (int i = 0; i < k; i++) {                  // reverse this group onto it
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;                                   // new head of this group
}

The elegance: by solving the rest of the list first, the already-correct remainder becomes the initial prev. The reversal loop then stitches automatically — the group's last node ends up pointing at it with no extra code.

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

Counter-questions on this approach

⭐ "Where does the stitching happen? I don't see it."

It's hidden in the initial value of prev. Normally reversal starts with prev = null, so the first node reversed becomes the tail pointing at null. Here prev starts as the head of the already-reversed remainder — so when the group's original first node gets cur.next = prev, it is pointing straight at the next group.

That's why solving the rest first is worth the stack: it turns the stitch into the reversal's own initialization.

⭐ "Why count k nodes before touching anything?"

Because a partial group must be left untouched, and reversal is destructive. If I reversed first and then discovered only two nodes remained with k = 3, the damage is already done and un-reversing means a second pass. Checking first costs O(k) per group — O(n) overall, the same as the reversal itself.

"What's the stack depth, and does it matter?"

n/k frames. Worst case k = 1, giving 5000 frames — which is survivable but uncomfortably close to the default JVM stack. Note k = 1 means "reverse every single node individually", i.e. return the list unchanged, so it's a degenerate case worth short-circuiting. I'd mention the iterative version as the one I'd actually ship.

"Why return prev at the end?"

After reversing k nodes, prev sits on the last node processed — the group's original last node, which is now its first. That's the head of this group and what the caller must attach to.

Approach 3 — Iterative with explicit stitching (optimal)

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0, head);
    ListNode groupPrev = dummy;                    // node just before the current group

    while (true) {
        ListNode kth = groupPrev;                  // walk k ahead to find the group's last node
        for (int i = 0; i < k && kth != null; i++) kth = kth.next;
        if (kth == null) break;                    // fewer than k remain — done

        ListNode groupNext = kth.next;             // first node AFTER the group

        // reverse the group, seeding prev with what follows it — stitches the tail for free
        ListNode prev = groupNext, cur = groupPrev.next;
        while (cur != groupNext) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        ListNode newGroupPrev = groupPrev.next;    // the old first node is now the group's LAST
        groupPrev.next = kth;                      // stitch the head: predecessor → new first
        groupPrev = newGroupPrev;                  // advance for the next group
    }
    return dummy.next;
}

Trace — [1,2,3,4,5], k = 2:

Result [2,1,4,3,5] ✓

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Why seed prev = groupNext instead of null?"

Same trick as the recursion, made explicit. Starting from null would leave the group's last node pointing at nothing, severing the rest of the list — then I'd need a separate line to reattach it.

Seeding with groupNext means the very first assignment cur.next = prev already points the group's new tail at the next group. One of the two stitches is free.

⭐ "Why while (cur != groupNext) rather than a counter?"

Because groupNext is a precise, already-computed boundary, so the loop terminates on the structure rather than on arithmetic. A counter would work identically but it duplicates information I already have, and an off-by-one in the counter is silent whereas the boundary is exact.

⭐ "Why save groupPrev.next before rewiring it?"

Because groupPrev.next is the group's original first node, which reversal turns into the group's last node — and that's exactly the groupPrev for the next round. Once I execute groupPrev.next = kth, that reference is gone.

This is the same save-your-escape-route discipline as question 1, applied to the loop variable rather than to a node pointer.

"Why does kth start at groupPrev rather than at the group's first node?"

So that advancing exactly k times lands on the group's last node rather than one past it. Starting at groupPrev — the node before the group — the k-th hop reaches the k-th node of the group. Starting at the first node, k hops would overshoot by one.

"What if k is 1?"

Each group is a single node, the reversal loop runs once and rewires it to itself-adjacent correctly, and the list comes out unchanged — which is the right answer. It does n rounds of O(1) work, so still O(n).

"What if k equals n?"

One group, one full reversal, no partial tail — it degenerates exactly to question 1.

Comparison

4. Why the Optimal Wins

All three are O(n) time. The array version is disqualified outright for mutating values rather than links.

Between the two pointer solutions, the recursion is genuinely elegant — solving the rest first makes the stitch disappear into the reversal's initialization — but it costs n/k stack frames, and at k = 1 that's 5000 deep. The iterative version achieves the same trick explicitly by seeding prev = groupNext, at O(1) space.

The framing worth keeping:

When reversing a segment that must stay connected, seed prev with what comes after the segment. The reversal then stitches its own tail, and only the head stitch is left to do by hand.

And the check-before-you-cut discipline: verify k nodes exist before reversing, because the operation is destructive and you can't cheaply take it back.

5. Java Prerequisites

Reversal bounded by a sentinel node rather than a count

ListNode prev = groupNext, cur = groupPrev.next;
while (cur != groupNext) {
    ListNode next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}

Looking ahead k with a null guard

ListNode kth = groupPrev;
for (int i = 0; i < k && kth != null; i++) kth = kth.next;
if (kth == null) break;

The && kth != null is essential — without it, a short tail throws NullPointerException.

Saving a pointer you are about to overwrite

ListNode newGroupPrev = groupPrev.next;   // before groupPrev.next = kth

Dummy with an initial next — new ListNode(0, head) — so the first group has a predecessor.

6. Interview Communication Guide

Clarifying questions: Leave a trailing partial group unreversed, or reverse it too (leave it — confirm, it changes the loop)? May I modify values, or only links (links only — this rules out the array approach)? Is O(1) space required (ask; it decides iterative vs recursive)? Can k exceed the list length (then nothing is reversed)?

The pitch

"The reversal itself is question 1 with a counter. What makes this hard is the stitching — after reversing a group, the node before it must point at the group's new first node, and the group's new last node must point at the next group.

Two things I'd get right up front. First, I have to check that k nodes remain before reversing anything, because a partial group must be left untouched and reversal is destructive — I can't discover the shortage afterwards and cheaply undo it. Second, I use a dummy head so the first group has a predecessor to rewire, like every other list-building problem in this section.

The trick that makes the code short: instead of seeding the reversal with prev = null, I seed it with groupNext — the first node after the group. Then the very first pointer flip already connects the group's new tail to the next group, so the tail stitch is free. Only the head stitch is left, which is one assignment: groupPrev.next = kth.

One subtlety: before doing that assignment I save groupPrev.next, because the group's original first node becomes its last, and that's exactly the groupPrev for the next round.

O(n) time, O(1) space. There's a recursive version that's arguably prettier — solving the rest of the list first makes the stitch vanish into the initialization — but it costs n/k stack frames, and at k = 1 that's 5000 deep."

Edge cases to volunteer:

Name k > n and the partial-tail case. The first crashes any look-ahead without a null guard; the second is the requirement most solutions get wrong by reversing the leftover.

7. Follow-Up Questions — Modified Constraints

⭐ "Reverse the trailing partial group too."

Drop the look-ahead check and reverse whatever remains. The code gets simpler — the if (kth == null) break; becomes "reverse from groupPrev.next to the end". Worth noting that the harder-sounding requirement is the easier one to implement; the "leave it alone" rule is what forces the look-ahead pass.

⭐ "Reverse alternate groups only — reverse the first k, skip the next k, and so on."

Same loop with a toggle. On skip rounds, just advance groupPrev by k without reversing. The look-ahead is still needed to decide whether a full group exists. This is LeetCode 2767-style and a natural extension once the stitching is factored out.

"Rotate the list right by k instead."

LeetCode 61, and a different technique entirely — find the length, connect the tail into a ring, walk to the new tail at position n − k % n, and break. Worth naming that it's not this problem, since the phrasing sounds similar.

"Swap nodes in pairs."

LeetCode 24 — this problem with k = 2, so the same code solves it. But the dedicated version is much simpler because with k = 2 there's no look-ahead loop and no inner reversal: just a.next = b.next; b.next = a. Recognising the general solution covers the specific case is worth saying; writing the simpler one when k is fixed is better engineering.

"What if it were a doubly linked list?"

Each reversal must also swap every node's prev, and the stitch has to fix prev on both boundary nodes. More bookkeeping, same structure — and the bugs are worse, because a broken back-pointer doesn't show up until someone traverses backwards.

"Could you do it without the look-ahead pass?"

Only by making reversal undoable — reverse the group, and if you discover it was short, reverse it back. That's correct and still O(n) overall, but it does up to 2k extra work on the final group and is harder to reason about. Counting first is cheaper and clearer.