Reverse Nodes in a Linked List in Groups of k

• Group processing – process the list in consecutive blocks of k nodes.
• Count first – walk k steps ahead to verify a full group exists before reversing.
• In-place reversal – reverse the k nodes using the standard previous-current-next technique.
• Dummy head – a sentinel node before the real head simplifies reconnection.
• Partial tail – a trailing group of fewer than k nodes is left unchanged.
• O(n) time, O(1) space – each node is touched a constant number of times.

What is the problem?

Given a singly linked list and a value k, reverse every group of k consecutive nodes. If the last group has fewer than k nodes, leave it unchanged. In a banking context, a settlement system at National Bank of India expects each batch of k records in reversed order.

How does the iterative approach work?

Use a dummy head to simplify edge cases. Keep a pointer groupPrev to the node before each group. For each group: (1) count k nodes ahead, (2) if fewer than k remain, stop, (3) reverse the k nodes, (4) reconnect.

package com.bank.service;

public class BatchReverser {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

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

        while (true) {
            // Check if k nodes remain
            ListNode kth = groupPrev;
            for (int i = 0; i < k; i++) {
                kth = kth.next;
                if (kth == null) return dummy.next;
            }
            ListNode groupNext = kth.next;

            // Reverse k nodes
            ListNode prev = groupNext;
            ListNode curr = groupPrev.next;
            for (int i = 0; i < k; i++) {
                ListNode tmp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = tmp;
            }

            // Reconnect
            ListNode groupFirst = groupPrev.next;
            groupPrev.next = prev;       // new front of reversed group
            groupPrev = groupFirst;      // old front is now the tail
        }
    }

    public static void main(String[] args) {
        // Build list: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode result = reverseKGroup(head, 3);
        StringBuilder sb = new StringBuilder();
        while (result != null) {
            sb.append(result.val);
            if (result.next != null) sb.append(" -> ");
            result = result.next;
        }
        System.out.println("Reversed in groups of 3: " + sb);
    }
}

Reversed in groups of 3: 3 -> 2 -> 1 -> 4 -> 5

Why use a dummy head?

The dummy head provides a stable reference to the node before the first group. Without it, the head of the list changes after the first reversal, complicating reconnection. The dummy eliminates the special case for the first group.

What are the three reconnection steps?

• After reversing a group:
• groupPrev.next = prev links the predecessor to the new front of the reversed group.
• The old first node of the group (now the tail) already points to groupNext because we initialised prev = groupNext before the reversal loop.
• groupPrev = groupFirst advances the predecessor to the tail for the next iteration.

What about the partial tail?

The counting loop checks for k nodes ahead. If fewer than k remain, the method returns immediately without reversing, leaving the partial tail in its original order. This is a deliberate specification detail that tests whether you read the requirements carefully.

What is the time and space complexity?

• Time: O(n) because each node is visited at most twice: once during counting and once during reversal.
• Space: O(1) because only a constant number of pointers are used.

What is the recursive alternative?

Recursively reverse the first k nodes, then set the old first node's next to the result of recursing on the rest. This is elegant but uses O(n/k) stack space.

public static ListNode reverseKGroupRecursive(ListNode head, int k) {
    ListNode curr = head;
    int count = 0;
    while (curr != null && count < k) { curr = curr.next; count++; }
    if (count < k) return head; // partial tail, leave as is

    ListNode prev = reverseKGroupRecursive(curr, k);
    curr = head;
    for (int i = 0; i < k; i++) {
        ListNode tmp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = tmp;
    }
    return prev;
}

What are common mistakes?

The most common mistake is losing the pointer to the rest of the list during reversal. Capturing groupNext before starting the reversal prevents this. Another is not handling the reconnection between groups correctly.

What should a senior engineer know?

A senior engineer prefers the iterative version for very long lists to avoid stack space proportional to the number of groups. The senior also knows that this technique of reversing and re-linking sublists appears in batch reordering, pagination of linked structures, and buffer manipulation in network protocols.