A settlement pipeline holds a singly linked list of pending transfers. Treasury wants every complete batch of k transfers flipped — last in the batch first — so a rollback walks that batch in reverse. A leftover batch shorter than k stays as it arrived. The intern dumped every amount into an ArrayList, reversed every full chunk of k, and allocated a new chain. The amounts were reversed. The transfer nodes were not. Downstream ledgers that still held a transfer node were following the same successor they always had.

Reverse nodes in k-group rewires every complete run of k nodes and leaves a leftover shorter than k alone. The linked list post owns dummy nodes and splice. Reverse Linked List owns the three-pointer rewire. Reverse Linked List II owns dummy-before-the-run, a bounded reverse, and the two links that splice the run back. Here we only care about repeating that splice until fewer than k nodes remain.

The problem

Given the head of a singly linked list and an integer k (k >= 1), reverse the nodes in groups of k and return the (possibly new) head. A leftover tail shorter than k stays in original order. k = 1 is the identity. Reverse by rewiring next, not by swapping values.

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8,  k=3  →  3 → 2 → 1 → 6 → 5 → 4 → 7 → 8
1 → 2 → 3 → 4 → 5,              k=2  →  2 → 1 → 4 → 3 → 5
1 → 2 → 3 → 4 → 5,              k=1  →  1 → 2 → 3 → 4 → 5
1 → 2 → 3 → 4 → 5,              k=5  →  5 → 4 → 3 → 2 → 1

A node is the usual two fields:

final class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

Note: In-place means the same node objects, new next links. Copying values into an array, reversing every full chunk of k, and building a fresh list passes a value-order test. The node that sat first in a batch is still first, now wearing a different number — or, if you allocated a new chain, it is a different object entirely. Reverse Linked List named that identity trap when the intern built a second chain.

Dump the list, reverse chunks, rebuild

Walk once, collect every value, reverse each complete window of k in the array, then allocate a new chain. Leftover indexes past the last full window are left as they were. Correct on values. Wrong on identity. Extra O(n) nodes.

ListNode reverseKGroupByValues(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) {
        int lo = i;
        int hi = i + k - 1;
        while (lo < hi) {
            int tmp = vals.get(lo);
            vals.set(lo, vals.get(hi));
            vals.set(hi, tmp);
            lo++;
            hi--;
        }
    }
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    for (int v : vals) {
        tail.next = new ListNode(v);
        tail = tail.next;
    }
    return dummy.next;
}

Every listener still holding a node thinks the successors never changed — because they are holding objects that are no longer in the list you returned. You paid a second chain for a question the original nodes already answer by rewiring next.

Dummy, count k, reverse that run, splice

A dummy in front of head gives every group — including the first, which may become the new head — a predecessor, so a group that starts at the old head is not a special case. before starts on dummy. Each iteration:

  1. Walk k steps from before. If you hit null before k nodes, the leftover is shorter than k — stop and return dummy.next. Do not reverse those nodes.
  2. Otherwise those k nodes are a complete group. Reverse that run and splice it back exactly as Reverse Linked List II does: before is the node before the run, the run length is k. Same bounded reverse, same two splice assignments. Do not re-derive the three pointers here.
  3. After the splice, the old first node of the group is now its tail. Move before onto that tail so the next count starts at the following group.

Walk k = 3 on 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8:

dummy → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → null    k=3

count 3 from dummy.next: 1, 2, 3 exist
  reverse that run (Reverse II, length 3):
    dummy → 3 → 2 → 1 → 4 → 5 → 6 → 7 → 8
  before moves to 1  (old group head, now group tail)

count 3 from 1.next: 4, 5, 6 exist
  reverse:
    dummy → 3 → 2 → 1 → 6 → 5 → 4 → 7 → 8
  before moves to 4

count 3 from 4.next: 7, 8, then null — leftover shorter than k
  stop

return dummy.next   →  3 → 2 → 1 → 6 → 5 → 4 → 7 → 8

When the first group includes the old head, dummy.next is the new head after the first splice. Returning the original head would hand back the tail of that first reversed group. reverseRun is the Reverse Linked List II splice; it returns the old group head, now the tail, so the next probe starts at the following group.

ListNode reverseKGroup(ListNode head, int k) {
    if (k == 1 || head == null) {
        return head;
    }
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode before = dummy;
    while (true) {
        ListNode probe = before;
        for (int i = 0; i < k; i++) {
            probe = probe.next;
            if (probe == null) {
                return dummy.next;
            }
        }
        before = reverseRun(before, k);
    }
}

ListNode reverseRun(ListNode before, int k) {
    ListNode tail = before.next;
    ListNode prev = null;
    ListNode current = tail;
    for (int i = 0; i < k; i++) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    before.next = prev;
    tail.next = current;
    return tail;
}

Time is O(n) — each node is probed at most once to confirm a full group, then visited once in the reverse. Space is O(1) besides the dummy and the handful of pointers.

If you reverse a leftover shorter than k, 1 → 2 → 3 → 4 → 5 with k = 3 becomes 3 → 2 → 1 → 5 → 4. The prompt wants 3 → 2 → 1 → 4 → 5. The probe that returns on null is the whole difference. And after a splice, before must become the tail of the group you just reversed — the old first node. That is why reverseRun returns tail, not prev. Leave before on dummy and every later group splices at the front. Move it onto prev (the new group head) and you sit at the wrong end of the run you just flipped.

k == 1 is already reversed. The early return is optional — groups of one plus splice are a no-op if you keep the handles — but it makes the identity obvious at the board.

What interviewers usually poke next

  • Leftover must stay. They will ask what happens when n % k != 0. Name the probe. The wrong answer is “reverse the remainder too” — that is a different problem.
  • k = n. The whole list. Same dummy and one group. You should be able to say this is Reverse Linked List with a dummy you did not need there.
  • Swap nodes in pairs. That is this problem with k = 2. Name the handles; do not start writing a pairs-only solution unless they ask.
  • Recursive version. Reverse the first k (or return head if fewer remain), recurse on the rest, attach the reversed group’s new tail to the recursive head. Mention the O(n / k) stack bill.
  • Do it by swapping values. Correct for value-order tests, O(n) extra space if you buffer a chunk, and you should say why in-place rewiring is the list they actually handed you.

You are done with this problem when you can reverse 1..8 in groups of 3 without flipping 7 and 8, and you can name why before becomes the tail of the group you just reversed.