Reverse Nodes In K Group

HARD✓ CHIP-TIMEDLC #25 — FULL STATEMENT ↗

The drill: Reverse a linked list in fixed-size chunks of k nodes each, leaving any final undersized chunk exactly as it was found.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A singly linked list and a group size k arrive together. The list needs to be walked in consecutive chunks of k nodes, with every full chunk reversed in place.

Chunks are counted strictly from the front: the first k nodes form one group, the next k form the next, and so on. If the nodes remaining at the end number fewer than k, that final partial group stays exactly as found — untouched and unreversed.

Node values themselves never change; only the links between nodes get rewired, so the same nodes end up rearranged into their new order.

EX 01

head = [10, 20, 30, 40, 50] · k = 2

→ [20, 10, 40, 30, 50]

TWO FULL GROUPS PLUS A LEFTOVER SINGLETON

EX 02

head = [1, 2, 3, 4, 5, 6] · k = 3

→ [3, 2, 1, 6, 5, 4]

EXACTLY TWO FULL GROUPS OF THREE

EX 03

head = [7] · k = 1

→ [7]

SINGLE NODE, K = 1

k is a positive integer no larger than the list's length
the list can hold anywhere from zero to a few thousand nodes
a trailing group shorter than k is left in its original order
only pointers are rearranged — node values are never copied or altered

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Reversing the whole list is a familiar pattern — this problem only adds a window size. What has to happen differently once a trailing chunk turns out shorter than that window?

HINT 2 THE STRUCTURE

Before flipping any pointers in a group, first confirm the group actually holds k nodes by walking ahead — a group that comes up short must be left untouched, not partially reversed.

HINT 3 ONE STEP FROM THE ANSWER

Reverse exactly k nodes with the same three-pointer flip used to reverse a whole list, then reconnect: the previous group's tail now points at this group's new head, and this group's old head — now its tail — points at the next group's start.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE K-GROUP FLIPPATTERN · IN-PLACE K-GROUP FLIPhead = [10, 20, 30, 40, 50] · k = 2

STEP 1

Reverse in fixed chunks of k=2: [10, 20, 30, 40, 50] splits into groups [10,20], [30,40], and a leftover [50] too short to flip.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/reverse-nodes-in-k-group.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        group_prev = dummy

        while True:
            # walk k nodes ahead — a short trailing group is left untouched
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next
            group_next = kth.next

            # reverse the k nodes between group_prev and kth
            prev, curr = group_next, group_prev.next
            while curr != group_next:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt

            new_start = kth              # old tail is the new head
            old_start = group_prev.next  # old head is now the tail
            group_prev.next = new_start
            group_prev = old_start

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 26 LN

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        vals = []
        node = head
        while node:
            vals.append(node.val)
            node = node.next

        n = len(vals)
        i = 0
        while i + k <= n:
            vals[i:i + k] = vals[i:i + k][::-1]
            i += k

        dummy = ListNode()
        tail = dummy
        for v in vals:
            tail.next = ListNode(v)
            tail = tail.next
        return dummy.next

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 20 LN

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode groupPrev = dummy;

        while (true) {
            // walk k nodes ahead — a short trailing group is left untouched
            ListNode kth = groupPrev;
            for (int i = 0; i < k; i++) {
                kth = kth.next;
                if (kth == null) {
                    return dummy.next;
                }
            }
            ListNode groupNext = kth.next;

            // reverse the k nodes between groupPrev and kth
            ListNode prev = groupNext;
            ListNode curr = groupPrev.next;
            while (curr != groupNext) {
                ListNode nxt = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nxt;
            }

            ListNode newStart = kth;             // old tail is the new head
            ListNode oldStart = groupPrev.next;   // old head is now the tail
            groupPrev.next = newStart;
            groupPrev = oldStart;
        }
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 33 LN

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        List<Integer> vals = new ArrayList<>();
        for (ListNode n = head; n != null; n = n.next) {
            vals.add(n.val);
        }

        int sz = vals.size();
        for (int i = 0; i + k <= sz; i += k) {
            Collections.reverse(vals.subList(i, i + k));
        }

        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        for (int v : vals) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 21 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED