Free lesson · DSA Mastery - Interview Prep, End to End

Reverse Nodes in k-Group

Medium7 min readdsalinked-list

Reverse Nodes in k-Group

Reverse Nodes in k-Group is the grand generalization of this sub-group: reverse every consecutive block of k nodes, leaving any final block shorter than k untouched. It's sublist reversal applied repeatedly - combining the boundary-walking, counted reversal, and seam-stitching from the previous topic, advancing a group anchor across the whole list. We present both the iterative approach (a dummy-anchored loop that reverses one group at a time and reconnects) and the recursive approach (reverse the first k, then recurse on the rest). Swap Nodes in Pairs (15.7) was this with k = 2; now k is arbitrary.

The key discipline: before reversing each group, verify that k nodes remain - if fewer, leave them as-is. Then reverse exactly k nodes and stitch the reversed block between the previous group's tail and the next group's head.

The Problem

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

Input:  head = [1, 2, 3, 4, 5], k = 2
Output: [2, 1, 4, 3, 5]

Explanation: Groups (1,2) and (3,4) reversed; 5 left alone.

Example 2:

Input:  head = [1, 2, 3, 4, 5], k = 3
Output: [3, 2, 1, 4, 5]

Explanation: Group (1,2,3) reversed; (4,5) too short, left alone.

Constraints:

• The number of nodes is n, with 1 <= k <= n <= 5000.
• 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

Approaches Overview

Both reverse each full group in O(n) total. The iterative version meets the O(1)-space follow-up; the recursive version is concise but uses stack depth proportional to the number of groups.

Approach 1: Iterative - Optimal

The Idea

Use a groupPrev anchor starting at a dummy. For each group: first check that k nodes remain by walking k steps from groupPrev (if you fall off the end, stop - the remainder stays as-is). Identify kth (the group's last node) and groupNext = kth.next. Reverse the group's k nodes using the three-pointer dance, stopping at groupNext. Then reconnect: groupPrev.next becomes kth (the new group head), and the old group head (now the tail) points to groupNext. Advance groupPrev to the group's new tail and repeat.

Logic Flowchart

graph TD
    A["dummy -> head; groupPrev = dummy"] --> B["kth = walk k nodes from groupPrev"]
    B --> C{"kth == null? (fewer than k left)"}
    C -->|Yes| D["Return dummy.next"]
    C -->|No| E["groupNext = kth.next"]
    E --> F["reverse group [groupPrev.next .. kth] stopping at groupNext"]
    F --> G["reconnect: tail = groupPrev.next (old head)"]
    G --> H["groupPrev.next = kth (new head)"]
    H --> I["groupPrev = tail (advance anchor)"]
    I --> B

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style I fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows the iterative k-group reversal. From a dummy anchor, we walk k nodes to find the group's last node; if fewer than k remain, we stop. Otherwise we reverse the group up to the next group's head, then reconnect the anchor to the new group head and advance the anchor to the group's new tail.

Code

public static ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode groupPrev = dummy;

    while (true) {
        // find the k-th node from groupPrev
        ListNode kth = groupPrev;
        for (int i = 0; i < k && kth != null; i++) kth = kth.next;
        if (kth == null) break;                  // fewer than k nodes remain

        ListNode groupNext = kth.next;
        // reverse the group: [groupPrev.next .. kth], stopping at groupNext
        ListNode prev = groupNext, cur = groupPrev.next;
        while (cur != groupNext) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        // reconnect
        ListNode newTail = groupPrev.next;       // old head is the new tail
        groupPrev.next = kth;                    // kth is the new group head
        groupPrev = newTail;                     // advance anchor to group tail
    }
    return dummy.next;
}

// Usage:
// reverseKGroup([1,2,3,4,5], 2) -> [2,1,4,3,5]
// reverseKGroup([1,2,3,4,5], 3) -> [3,2,1,4,5]

This Java code anchors a group-prev at a dummy. For each group it walks k nodes to find the last one, stopping if fewer than k remain. It reverses the group with the three-pointer technique, stopping at the next group's head, then reconnects the anchor to the new head and advances the anchor to the group's new tail. It uses constant space.

Step-by-Step Walkthrough

A frame-by-frame trace on [1, 2, 3, 4, 5], k = 2:

graph LR
    F0["groupPrev=dummy<br/>kth=2; groupNext=3"]
    F1["reverse (1,2)→(2,1)<br/>dummy→2→1→3...<br/>groupPrev=1"]
    F2["kth=4; groupNext=5<br/>reverse (3,4)→(4,3)<br/>1→4→3→5; groupPrev=3"]
    F3["walk k from 3 → null<br/>fewer than 2 left: stop"]
    F4["result 2,1,4,3,5"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough reverses one through five in groups of two. The first group one, two becomes two, one. The second group three, four becomes four, three. Only node five remains, fewer than two, so it stays. The result is two, one, four, three, five.

Result: [2, 1, 4, 3, 5].

Complexity

Time: O(n) - each node is reversed once and counted once. Space: O(1).

Approach 2: Recursive

The Idea

Check whether k nodes remain from the current head. If not, return head unchanged (the short tail). Otherwise reverse the first k nodes, then recursively reverse the rest and attach it: the original head becomes the group's tail, and its next is the result of recursing on the (k+1)-th node. Concise, mirroring the iterative logic, but uses O(n/k) stack depth.

Logic Flowchart

graph TD
    A["reverseKGroup(head, k)"] --> B["walk k nodes; enough?"]
    B -->|No| C["Return head (short tail unchanged)"]
    B -->|Yes| D["reverse first k nodes (head becomes tail)"]
    D --> E["head.next = reverseKGroup(k+1-th node, k)"]
    E --> F["Return new group head (k-th node)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the recursive approach. If fewer than k nodes remain, return the head unchanged. Otherwise reverse the first k nodes, recurse on the rest, and attach the original head, now the group's tail, to the recursively processed remainder.

Code

public static ListNode reverseKGroupRecursive(ListNode head, int k) {
    // check k nodes remain
    ListNode node = head;
    for (int i = 0; i < k; i++) {
        if (node == null) return head;       // fewer than k: leave as is
        node = node.next;
    }
    // reverse first k nodes
    ListNode prev = null, cur = head;
    for (int i = 0; i < k; i++) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    // head is now the tail of this group; attach the recursively processed rest
    head.next = reverseKGroupRecursive(cur, k);
    return prev;                              // new head of this group
}

This Java code checks that k nodes remain, returning the head unchanged if not. It reverses the first k nodes, then attaches the original head, now the group's tail, to the recursively reversed remainder, returning the new group head.

Complexity

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

Complexity Comparison

Both O(n) time. The iterative version is the expected answer for O(1) space; the recursion is elegant and concise but uses stack depth proportional to the group count. Both must check for a full group of k before reversing.

Variations & Follow-ups

How does this generalize Swap Nodes in Pairs (15.7)?

Swap Pairs is exactly k = 2. The "reverse a fixed-size block, then advance the anchor" structure is identical; k-group just makes the block size a parameter and adds the "leave a short final block" rule.

Why check for k nodes before reversing?

If fewer than k remain, those nodes must stay in original order. Reversing first and undoing later would be wasteful and error-prone; verifying up front cleanly skips the short tail.

What if the problem wanted the short tail reversed too?

Then you'd reverse whatever remains regardless of count - a minor change (drop the "enough nodes" guard for the last block). The standard problem leaves it untouched.

What about edge cases?

• k = 1: No change (each "group" is one node).
• k = n: Reverse the entire list once.
• n not a multiple of k: Final short block left as-is (Example 2).
• Single node: Returned unchanged.

Common Interview Pitfalls

• Reversing a final block shorter than k. Must check the count first and leave it.
• Botching the seam reconnection. Track groupPrev, kth, groupNext, and the new tail (old head) carefully.
• Forgetting to advance the anchor to the group's new tail. The old head becomes the tail and the next anchor.
• Stopping the reversal at the wrong node. Reverse until cur == groupNext, not until null.

Why This Problem Matters

Reverse Nodes in k-Group is the capstone of in-place reversal: it composes boundary-walking, counted three-pointer reversal, and seam-stitching, applied iteratively across the list. Mastering it means the entire reversal family - full, partial, grouped - is one coherent technique in your hands, and the "process fixed-size blocks with an advancing anchor" structure transfers to many chunked-traversal problems.

This completes the In-place Reversal sub-group (15.20–15.24). The final sub-group, Fast and Slow Pointers, opens with an Introduction to the tortoise-and-hare technique you've already glimpsed in middle-finding and palindrome checking - now developed fully for cycle detection, cycle-entrance location, and even problems that aren't linked lists at all.

Back to DSA Mastery - Interview Prep, End to End