☕ DSA Java Articles

Topics › Linked List › Hard Problems of LL

Reverse LL in group of given size K

Hard TUF ID 614 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the head of a singly linked list and a positive integer k, reverse the nodes of the list k at a time and return the new head. Cut the list into consecutive blocks of k nodes from the front; reverse each full block in place. If the number of nodes is not a multiple of k, the final block has fewer than k nodes and stays in its original order. You must change the links between nodes; changing the values stored in them is not allowed in the strict version.

Constraints: 1 ≤ k ≤ n ≤ 5000. The follow-up asks for O(1) extra memory.

Some versions of this problem also reverse the last, shorter block. The ideas below adapt easily: where they detect a short final block and leave it alone, reverse it instead.

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

Example 1

head = 1 -> 2 -> 3 -> 4 -> 5, k = 2
answer = 2 -> 1 -> 4 -> 3 -> 5        // blocks [1 2] [3 4] are reversed, [5] is too short

Example 2

head = 1 -> 2 -> 3 -> 4 -> 5, k = 3
answer = 3 -> 2 -> 1 -> 4 -> 5        // only the first block is full

Approach 1: Brute force, rearrange the values

Intuition. If we were allowed to touch values, the task would be an array exercise: copy the values into a list, reverse every full window of size k, and write the values back into the nodes in order. The list structure never changes. This is worth seeing because it pins down exactly what output is expected, and it serves as a reference to test the real solutions against. It breaks the “change links, not values” rule, so it is not an acceptable final answer.

Algorithm.

  1. Copy all values into an ArrayList.
  2. For start = 0, k, 2k, ... while start + k ≤ size, reverse the sub-list [start, start + k).
  3. Walk the list again, overwriting each node’s value with the next value from the array.
static ListNode bruteForce(ListNode head, int k) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode cur = head; cur != null; cur = cur.next) vals.add(cur.val);
    for (int start = 0; start + k <= vals.size(); start += k) {
        Collections.reverse(vals.subList(start, start + k));   // the partial last block is skipped
    }
    ListNode cur = head;
    for (int v : vals) {
        cur.val = v;
        cur = cur.next;
    }
    return head;
}

Complexity. Time O(n): one copy, one reversal pass over at most n values, one write-back. Space O(n) for the copy.

subList returns a view, so Collections.reverse on it reverses that window of the original ArrayList directly.

Approach 2: Better, recursion

Intuition. Solve the first block yourself and let recursion solve the rest. Suppose the recursive call has already returned the head of the correctly processed remainder, call it rest. Reversing the first k nodes is then the textbook three-pointer reversal, with one twist: instead of starting prev at null, start it at rest. The old first node of the block becomes the block’s last node, and its next automatically ends up pointing at rest. The old k-th node becomes the new head and is returned.

Before doing anything we walk k nodes to make sure the block is full. If we hit null first, this is the short final block, and we return it unchanged.

Algorithm.

  1. Walk k nodes from head with a pointer cur. If the list ends first, return head.
  2. cur is now the first node of the next block. Call prev = recursive(cur, k).
  3. Reverse the nodes from head up to (not including) cur, starting with prev as the initial “previous” node.
  4. Return prev, which is the old k-th node.
static ListNode recursive(ListNode head, int k) {
    ListNode cur = head;
    for (int i = 0; i < k; i++) {
        if (cur == null) return head;               // fewer than k nodes left: leave them alone
        cur = cur.next;
    }
    ListNode prev = recursive(cur, k);              // cur is the first node of the next group
    ListNode node = head;
    while (node != cur) {                           // reverse this group; its old head ends up pointing at prev
        ListNode nxt = node.next;
        node.next = prev;
        prev = node;
        node = nxt;
    }
    return prev;                                    // the old k-th node is the new head of this group
}

Complexity. Time O(n): every node is visited once by the counting walk and once by the reversal. Space O(n / k) for the recursion stack, one frame per block. For k = 1 that is n frames, which is why this is “better” and not “optimal”.

Approach 3: Optimal, iterative reversal with a dummy head

Intuition. The recursion only needs the stack to remember where the next block starts. We can carry that information in variables instead. Put a dummy node in front of the list so that the first block has a predecessor like every other block. Keep groupPrev, the last node of the part that is already finished. For each block:

Algorithm.

  1. Create dummy with dummy.next = head, and set groupPrev = dummy.
  2. Repeat: kth = kthNode(groupPrev, k); stop if it is null.
  3. Reverse the nodes from groupPrev.next to kth, with prev initialised to kth.next.
  4. Save oldFirst = groupPrev.next, set groupPrev.next = kth, then groupPrev = oldFirst.
  5. Return dummy.next.
static ListNode optimal(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode groupPrev = dummy;                     // last node of the part that is already done
    while (true) {
        ListNode kth = kthNode(groupPrev, k);       // last node of the current group
        if (kth == null) break;                     // fewer than k nodes remain
        ListNode groupNext = kth.next;
        ListNode prev = groupNext, cur = groupPrev.next;
        while (cur != groupNext) {                  // reversed group's tail will point at groupNext
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        ListNode oldFirst = groupPrev.next;         // now the last node of the reversed group
        groupPrev.next = kth;
        groupPrev = oldFirst;
    }
    return dummy.next;
}

static ListNode kthNode(ListNode start, int k) {
    while (start != null && k > 0) {
        start = start.next;
        k--;
    }
    return start;
}

Dry run on Example 1 (1 2 3 4 5, k = 2):

round groupPrev kth groupNext list after the round
1 dummy 2 3 dummy → 2 → 1 → 3 → 4 → 5
2 1 4 5 dummy → 2 → 1 → 4 → 3 → 5
3 3 null (only 5 left) - stop

In round 1, the reversal makes 1.next = 3 (because prev started at groupNext = 3) and 2.next = 1. Setting dummy.next = 2 finishes the splice, and groupPrev moves to node 1, the tail of the reversed block.

Complexity. Time O(n): kthNode walks each node once while checking blocks (plus at most k - 1 nodes of the final partial block), and each node is reversed once. Space O(1): a fixed number of pointers.

The Java tests verify that the two link-based methods return exactly the original node objects in the new order, so they really relink rather than copy.

Edge cases and pitfalls