24. Reverse Nodes in k-Group

Extract all values into an array, reverse each k-sized chunk in the array, then build a new linked list from the modified array.

Brute Force

Traverse the list to collect all values into an array. Then for each complete group of k elements, reverse that segment in the array. Finally, rebuild the linked list from the array.

This is straightforward but uses O(n) extra space for the array and doesn't practice in-place linked list manipulation.

Time is O(n) for traversal, O(n) for chunk reversal, O(n) for rebuilding = O(n) total. Space is O(n) for the array.

Why it's not ideal: it doesn't reverse the list in place and uses extra space proportional to the list length.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

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

    public ListNode reverseKGroup(ListNode head, int k) {
        List<Integer> values = new ArrayList<>();
        ListNode node = head;
        while (node != null) {
            values.add(node.val);
            node = node.next;
        }

        int n = values.size();
        for (int i = 0; i + k <= n; i += k) {
            int left = i, right = i + k - 1;
            while (left < right) {
                int temp = values.get(left);
                values.set(left, values.get(right));
                values.set(right, temp);
                left++;
                right--;
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int v : values) {
            current.next = new ListNode(v);
            current = current.next;
        }
        return dummy.next;
    }
}

Walk the list in chunks of k. For each complete chunk, reverse the k nodes in place by rewiring their next pointers. Connect each reversed group to the next one.

Mental Model

Think of the list as a train of carriages grouped into sections of k. For each section, we unhook the carriages and reattach them in reverse order. If the last section has fewer than k carriages, we leave them as-is.

Algorithm Steps

1. Create a dummy node pointing to head. Set group_prev = dummy.
2. Count ahead: From group_prev, walk k steps to find group_end. If we can't reach k nodes, stop (remaining nodes stay as-is).
3. Reverse the group: Reverse the k nodes between group_prev.next and group_end by iterating with prev/curr/nxt pointers.
4. Reconnect: After reversal, the old first node of the group is now the last. Set group_prev.next to the new first (old last) and connect the old first's next to what comes after the group.
5. Set group_prev to the old first node (now the tail of the reversed group) and go to step 2.
6. Return dummy.next.

Worked Walk-through

Example: [1,2,3,4,5], k = 2

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

Edge Cases

• k = 1: No reversal needed. Every group of 1 is trivially reversed.
• k = n: Reverse the entire list.
• n not divisible by k: The last group with fewer than k nodes is left unchanged.

Complexity

• Time: O(n) — each node is visited a constant number of times (once for counting, once for reversing).
• Space: O(1) — only pointer variables, no extra data structures.