Reverse Nodes in k-Group: the cost of counting before you cut

The problem sounds deceptively close to "Reverse Linked List" (206). It is not. The extra ingredient — reversing only in groups of exactly k, leaving the tail alone if it falls short — turns a single traversal into a rhythm: count, verify, reverse, stitch, advance. Miss any one of those beats and you either corrupt the list or incorrectly flip a partial tail.

The constraints say 1 <= k <= n <= 5000 and node values in [0, 1000]. Neither bound is large, but the follow-up asks for O(1) extra space, which rules out the simplest approach immediately. Let me work through all three approaches the source covers, because the progression from O(n) to O(1) space is the real lesson here.

The problem

Given the head of a linked list, reverse the nodes in groups of k at a time and return the modified list. If the number of remaining nodes is not a multiple of k, those trailing nodes must stay in their original order. You may only change the node links — not the node values. Full statement: LeetCode 25.

Constraints:
- The number of nodes in the list is n.
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000

What the constraints force

n <= 5000 means O(n²) would still pass, but the problem is really O(n) — you visit each node at most twice (once to count the group, once to reverse). The bounded value range [0, 1000] is irrelevant; this problem is pure pointer surgery, values do not factor in at all.

The critical structural constraint is that you cannot alter node values — only pointers. That eliminates any approach based on collecting values, sorting, then writing them back. You have to move the nodes themselves.

k is always valid (k <= n), so you never get a case where the entire list is shorter than k. But partial tails (when n is not a multiple of k) are guaranteed whenever n % k != 0, and those must be left untouched.

Approach 1: collect nodes into an array, reverse in-place, rewire

The most direct translation of the problem: forget pointer manipulation for a moment and just move the nodes as objects. Collect them all into a list, reverse each group of k in that list using two-pointer swapping, then rewire the next pointers to match the new order.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if not head or k == 1:
            return head
 
        # Collect all nodes into an array
        nodes = []
        current = head
        while current:
            nodes.append(current)
            current = current.next
 
        n = len(nodes)
        # Reverse each complete group of k in-place
        for i in range(0, n - n % k, k):
            left, right = i, i + k - 1
            while left < right:
                nodes[left], nodes[right] = nodes[right], nodes[left]
                left += 1
                right -= 1
 
        # Rewire next pointers
        for i in range(n - 1):
            nodes[i].next = nodes[i + 1]
        nodes[n - 1].next = None
 
        return nodes[0]

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}
 
public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;
 
        var nodes = new List<ListNode>();
        ListNode current = head;
        while (current != null) {
            nodes.Add(current);
            current = current.next;
        }
 
        int n = nodes.Count;
        for (int i = 0; i <= n - k; i += k) {
            int left = i, right = i + k - 1;
            while (left < right) {
                ListNode temp = nodes[left];
                nodes[left] = nodes[right];
                nodes[right] = temp;
                left++;
                right--;
            }
        }
 
        for (int i = 0; i < n - 1; i++) {
            nodes[i].next = nodes[i + 1];
        }
        nodes[n - 1].next = null;
 
        return nodes[0];
    }
}

The loop bound range(0, n - n % k, k) / i <= n - k is the key detail. n - n % k is the index of the last element in the last complete group. If n = 5 and k = 3, then n % k = 2, so we only process indices 0..2. Indices 3..4 stay in their original relative order because they were never swapped.

Complexity: Time O(n) — one pass to collect, O(n) to swap, O(n) to rewire. Space O(n) for the array. This is the approach the follow-up specifically asks you to beat.

Approach 2: iterative in-place — the O(1) space solution

This is the one I'd ship. The idea is to work group by group without materializing anything: find the kth node ahead (to verify group completeness), reverse the k nodes between group_prev and kth_node, then stitch the boundaries and advance.

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        group_prev = dummy
 
        while True:
            kth_node = self._get_kth(group_prev, k)
            if not kth_node:
                break
 
            group_next = kth_node.next
 
            # Reverse the group: prev starts at group_next (the tail anchor)
            prev, curr = kth_node.next, group_prev.next
            while curr != group_next:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt
 
            # Stitch: group_prev -> kth_node (new head of reversed group)
            #         old group head (now tail) -> group_next
            tmp = group_prev.next          # old group head, now tail
            group_prev.next = kth_node     # connect to reversed group's new head
            group_prev = tmp               # advance group_prev to the new tail
 
        return dummy.next
 
    def _get_kth(self, node: ListNode, k: int) -> ListNode:
        while node and k > 0:
            node = node.next
            k -= 1
        return node

public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode groupPrev = dummy;
 
        while (true) {
            ListNode kthNode = GetKth(groupPrev, k);
            if (kthNode == null) break;
 
            ListNode groupNext = kthNode.next;
 
            ListNode prev = kthNode.next;
            ListNode curr = groupPrev.next;
 
            while (curr != groupNext) {
                ListNode nxt = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nxt;
            }
 
            ListNode tmp = groupPrev.next;
            groupPrev.next = kthNode;
            groupPrev = tmp;
        }
 
        return dummy.next;
    }
 
    private ListNode GetKth(ListNode node, int k) {
        while (node != null && k > 0) {
            node = node.next;
            k--;
        }
        return node;
    }
}

Hand trace: [1, 2, 3, 4, 5], k = 3

Let me step through the first group precisely. The dummy node is at position 0, so group_prev = dummy.

Iteration 1:

_get_kth(dummy, 3) walks: dummy -> 1 -> 2 -> 3, returns node 3. That is kth_node.

group_next = node(4).

Now reverse from node(1) to node(3) with prev = node(4) as the tail anchor:

prev=4, curr=1:  1.next = 4,  prev=1, curr=2
prev=1, curr=2:  2.next = 1,  prev=2, curr=3
prev=2, curr=3:  3.next = 2,  prev=3, curr=4  (curr == group_next, stop)

After the inner loop, prev = node(3) which is the new head of the reversed group. The chain is 3 -> 2 -> 1 -> 4 -> 5.

Stitch: tmp = dummy.next (which is still node(1) at this point — the old head, now tail). dummy.next = node(3). group_prev = node(1).

List is now: dummy -> 3 -> 2 -> 1 -> 4 -> 5 -> null, with group_prev at node(1).

Iteration 2:

_get_kth(node(1), 3) walks: 1 -> 4 -> 5 -> null. Returns null because only 2 nodes remain after node(1). Loop breaks.

Final result: [3, 2, 1, 4, 5]. Correct.

The stitching logic is the part people get wrong. tmp = group_prev.next must be captured before group_prev.next = kth_node overwrites it. That single line of ordering is where most implementations fail.

Complexity: Time O(n) — each node is visited twice at most: once during the kth-node probe, once during the reversal. Space O(1) — three pointers, no additional structure.

Approach 3: recursion — elegant but watch the stack

The recursive formulation is the shortest to write and the easiest to verify at a glance.

Base case: if there are fewer than k nodes remaining, return head unchanged.

Recursive case: count forward k steps to verify group completeness, then recurse on the remainder first (depth-first), then reverse the current group pointing its tail at the result of the recursive call.

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        curr = head
        count = 0
        while curr and count < k:
            curr = curr.next
            count += 1
 
        if count < k:
            return head
 
        # curr now points to the head of the next group
        # Recurse first, then reverse current group around the result
        rest = self.reverseKGroup(curr, k)
 
        prev = rest
        curr = head
        for _ in range(k):
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
 
        return prev

public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
        ListNode curr = head;
        int count = 0;
        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }
 
        if (count < k) return head;
 
        ListNode rest = ReverseKGroup(curr, k);
 
        ListNode prev = rest;
        curr = head;
        for (int i = 0; i < k; i++) {
            ListNode nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
 
        return prev;
    }
}

The key insight: by recursing first and reversing second, the current group's original head (now its tail after reversal) can be directly assigned curr = rest — it naturally becomes the connector to the next already-reversed group.

Complexity: Time O(n) — every node is visited once at each level of recursion and the total work across all levels is O(n). Space O(n/k) — the recursion depth is exactly floor(n/k), the number of complete groups. In the worst case (k = 1), that is O(n) stack frames.

The k = 1 stack depth concern is somewhat theoretical in this problem since the constraints give k <= n <= 5000, but in Python where the default recursion limit is 1000, a list of 5000 nodes with k = 1 would actually hit the limit. That is a real bug, not a theoretical one.

Edge cases that matter

k = 1: No reversal needed. The iterative solution terminates correctly because _get_kth returns the first node, the reversal loop runs once (no-op since prev = group_next), and advances correctly. The recursive solution returns head after recursing on curr which is head.next — effectively rebuilds the list unchanged. The array solution swaps each group of one in-place, which changes nothing.

Tail shorter than k: This is the defining behavior of the problem. The iterative solution checks _get_kth returns None; the array solution's loop bound excludes the partial tail; the recursive solution returns head when count < k. All three handle it correctly but through different mechanisms — the array approach is arguably the most obvious.

n == k (entire list is one group): All three approaches reverse the entire list. No tail remainder. Worth testing explicitly to verify the stitching logic sets tail.next = null rather than leaving a dangling pointer.

n is a multiple of k: All groups complete, no tail. The iterative loop terminates when _get_kth returns None at the very end. The recursion terminates when the final group finds zero nodes remaining. Both clean.

Single node (n = 1, k = 1): Trivial — no reversal. All approaches return the input unchanged. The dummy node technique in the iterative solution specifically exists to avoid special-casing the head.

Comparison table

All three are O(n) time. The space story is what distinguishes them.

What I'd ship, and why

Iterative, without hesitation. The O(1) space guarantee is explicit in the follow-up, but more importantly the iterative version has no hidden failure modes — no recursion limit, no implicit stack, no dependency on how deep the call can go. The stitching logic (tmp = group_prev.next; group_prev.next = kth_node; group_prev = tmp) looks tricky on first read but reduces to: save the old head, connect the previous tail to the new head, advance the previous tail pointer. Once you trace through it once with a concrete example, it locks in.

The recursive version is beautiful and I would not reject it in a code review. But in production code where lists could be arbitrarily long, I do not want to explain why a k = 1 case crashes with a recursion error.

The array version exists to explain why you need something better. Never ship it.

The transferable pattern: group-chunked in-place pointer manipulation

This problem belongs to a family where you process a linked list in fixed-size windows, applying some transformation inside each window and carefully stitching the window boundaries. The core skill is maintaining four reference points simultaneously: the node before the group (group_prev), the first node of the group (the future tail), the last node of the group (the future head), and the first node of the next group. Losing track of any one of these four breaks the list.

That same four-pointer discipline shows up in problems that split and merge list segments, rotate lists by a fixed amount, or partition lists around a pivot — the specific operation inside each group changes, but the boundary management stays identical.

Where this sits in the linked list series

This problem arrives after Reverse Linked List (206), which established the three-pointer reversal technique, and after Reorder List (143), which required splitting and interleaving. Reverse Nodes in k-Group is the escalation: instead of reversing the whole list or a fixed split, you parameterize the reversal size and must handle the partial tail.

Swap Nodes in Pairs (24) is the special case k = 2. If this problem felt comfortable, go back and re-read 24 — you will notice the iterative solution is identical with k hardcoded to 2, and the recursive solution is one base case and one recursive call with the pair-swap inlined.

Reverse Linked List II (92) is the single-group variant: reverse exactly the nodes between positions left and right. The boundary stitching problem is the same; you just do it once rather than repeatedly.

Rotate List (61) is group processing without reversal. You find the new tail at position n - k % n, cut there, and reconnect the head. The "find the kth node from the end" helper you need is basically _get_kth in disguise.

Split Linked List in Parts (725) generalizes to uneven groups: distribute n nodes into k parts as evenly as possible, with earlier parts getting one extra when the division is uneven. The counting logic is more complex, but the segment-boundary management is the same pattern.