Reverse complete groups of k nodes in a Java linked chain

Last updated: 1 Oct 20264 min read

tutorial

Group reversal changes links within each complete run of k nodes and leaves a shorter final run in its original order.

Find the boundary before mutation

Starting from a sentinel before the current group, walk k links to locate its last node. If there are fewer than k nodes, stop before changing any link in that partial group. Save the node after the group, then reverse links until that saved boundary is reached.

After reversal, the old group head is the new tail. Connect the previous group's tail to the former last node and advance the group predecessor to the former head. Both links matter: skipping either can discard a suffix or form a cycle.

Define k and input ownership

Reject k less than one. A group size of one returns the same topology, while an empty chain stays empty. The method assumes an acyclic, exclusively mutable Node chain; it cannot operate on private nodes inside java.util.LinkedList.

If the requirement is to reverse the entire chain, whole-chain reversal is smaller. If it is to move a suffix to the front without reversing its order, use rotation.

Working program

public class ReverseDispatchGroups {
    static final class Node {
        final String dispatchId;
        Node next;
        Node(String dispatchId, Node next) { this.dispatchId = dispatchId; this.next = next; }
    }
    static Node reverseGroups(Node head, int groupSize) {
        if (groupSize <= 0) throw new IllegalArgumentException("group size must be positive");
        Node sentinel = new Node("sentinel", head), before = sentinel;
        while (true) {
            Node last = before;
            for (int step = 0; step < groupSize && last != null; step++) last = last.next;
            if (last == null) return sentinel.next;
            Node after = last.next;
            Node cursor = before.next, previous = after;
            while (cursor != after) {
                Node following = cursor.next;
                cursor.next = previous;
                previous = cursor;
                cursor = following;
            }
            Node oldHead = before.next;
            before.next = last;
            before = oldHead;
        }
    }
    static String labels(Node head) {
        StringBuilder result = new StringBuilder();
        for (Node cursor = head; cursor != null; cursor = cursor.next) {
            if (result.length() > 0) result.append(",");
            result.append(cursor.dispatchId);
        }
        return result.toString();
    }
    public static void main(String[] args) {
        Node head = new Node("load-15", new Node("seal-47", new Node("scan-82",
            new Node("pack-20", new Node("ship-35", null)))));
        System.out.println(labels(reverseGroups(head, 2)));
        System.out.println(reverseGroups(null, 3) == null);
    }
}

Output

seal-47,load-15,pack-20,scan-82,ship-35
true

Cost and ownership

Each node participates in a constant number of scans and link writes, giving O(n) time and O(1) extra references. One sentinel is allocated. Existing Node identities and payload objects are preserved.

Common Mistakes

Do not reverse a final group smaller than k when the contract says complete groups only.
Do not forget to reconnect the previous group to its new head.
Do not allow k equal to zero; the boundary scan would make no progress.