☕ DSA Java Articles

Topics › Linked List › Hard Problems of LL

Reverse LL in group of given size K

Hard TUF ID 2842 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list and a positive integer k. Reverse the nodes of the list k at a time: the first k nodes are reversed as a block, then the next k, and so on. If the number of nodes left at the end is less than k, those nodes stay in their original order. Return the head of the modified list. The intended solution rearranges the nodes themselves rather than swapping values, and uses only constant extra space.

Constraints: 0 ≤ n ≤ 5000, 1 ≤ k ≤ 5000, values fit in an int.

Example 1

head = 1 -> 2 -> 3 -> 4 -> 5, k = 2
answer = 2 -> 1 -> 4 -> 3 -> 5     // the trailing block [5] has fewer than k nodes and is left alone

Example 2

head = 1 -> 2 -> 3 -> 4 -> 5, k = 3
answer = 3 -> 2 -> 1 -> 4 -> 5

Example 3

head = 1 -> 2 -> 3 -> 4 -> 5, k = 6
answer = 1 -> 2 -> 3 -> 4 -> 5     // there is no full block at all

Approach 1: Brute force, reverse values in an array

Intuition. Reversing a block of a linked list is awkward because we cannot step backwards. Reversing a block of an array is trivial. So copy the values out, reverse every full block of k entries with two indices, and write the values back into the same nodes. The node objects never move; only their payloads change.

Algorithm.

  1. Copy the values into a list vals; let n be its size.
  2. For start = 0, k, 2k, ... while start + k <= n: swap vals[i] and vals[j] for i from start and j from start + k - 1 moving inward.
  3. Walk the linked list once more, writing vals back in order.
  4. Return head.
static ListNode bruteForce(ListNode head, int k) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode t = head; t != null; t = t.next) vals.add(t.val);
    int n = vals.size();
    for (int start = 0; start + k <= n; start += k) {
        for (int i = start, j = start + k - 1; i < j; i++, j--) {
            int tmp = vals.get(i);
            vals.set(i, vals.get(j));
            vals.set(j, tmp);
        }
    }
    ListNode t = head;
    for (int v : vals) { t.val = v; t = t.next; }
    return head;
}

Complexity. Time O(n): copying, reversing (each element is swapped at most once) and writing back are all linear. Space O(n) for the copied values.

The condition start + k <= n is what leaves a short final block untouched. This approach is correct and fast, but it fails the spirit of the problem: it needs linear extra memory, and because it moves values rather than nodes, it breaks any external references that expect a particular node to carry a particular value.

Approach 2: Better, recursion

Intuition. The problem has a natural recursive structure: “reverse the first block, then solve the same problem on the rest, then connect the two”. If we first check that a full block of k nodes exists, we can recurse on the node after the block, obtaining the already-processed remainder. Then we reverse the current block with the usual three-pointer loop, but seeding prev with the remainder’s head instead of null, so the block’s old first node (which becomes its tail) points straight at the processed rest.

Algorithm.

  1. Walk k steps from head, counting. If fewer than k nodes exist, return head unchanged.
  2. Let node be the first node after the block; recursively compute restReversed = better(node, k).
  3. Reverse the k nodes starting at head, with prev initialised to restReversed.
  4. Return prev, which is now the old k-th node and the new head of this block.
static ListNode better(ListNode head, int k) {
    ListNode node = head;
    int count = 0;
    while (node != null && count < k) { node = node.next; count++; }
    if (count < k) return head;                            // fewer than k nodes remain: leave them unchanged
    ListNode restReversed = better(node, k);              // node is the first node of the next block
    ListNode prev = restReversed, cur = head;
    for (int i = 0; i < k; i++) {                          // reverse this block; its old first node ends up pointing at the rest
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;                                           // the old k-th node is the new first node of the block
}

Complexity. Time O(n): each node is counted once and reversed once. Space O(n / k) for the recursion stack, one frame per block; with k = 1 that is O(n) frames.

The seeding trick is the heart of this version. In an ordinary reversal prev starts as null, so the old head ends up pointing at nothing. Starting prev at restReversed means the final cur.next = prev of the first iteration wires the block’s new tail to the rest of the answer, with no separate “connect” step.

The downside is the stack. For n = 5000 and k = 1 the recursion is 5000 deep, which is usually fine in Java but not something to rely on, and interviewers will ask for the iterative version.

Approach 3: Optimal, iterative block surgery

Intuition. Keep a pointer to the tail of the previous block (initially a dummy node in front of the head). From there, walk k steps to find the k-th node of the current block. If it does not exist, we are done. Otherwise, detach the block by cutting the link after the k-th node, reverse the block with the standard loop, and splice it back: the previous block’s tail now points to the k-th node (new block head), and the block’s old first node (new block tail) points to whatever followed the block. That old first node becomes the “previous block tail” for the next iteration.

Algorithm.

  1. Create dummy with dummy.next = head and set prevBlockTail = dummy.
  2. Loop:
    • Starting at prevBlockTail, walk k steps to kth. If kth is null, break.
    • Record blockStart = prevBlockTail.next and nextBlockStart = kth.next.
    • Set kth.next = null to isolate the block, then prevBlockTail.next = reverse(blockStart).
    • Set blockStart.next = nextBlockStart and prevBlockTail = blockStart.
  3. Return dummy.next.
static ListNode optimal(ListNode head, int k) {
    ListNode dummy = new ListNode(0, head);
    ListNode prevBlockTail = dummy;
    while (true) {
        ListNode kth = prevBlockTail;
        for (int i = 0; i < k && kth != null; i++) kth = kth.next;   // k-th node of the current block
        if (kth == null) break;                                      // fewer than k nodes remain
        ListNode blockStart = prevBlockTail.next, nextBlockStart = kth.next;
        kth.next = null;                                             // isolate the block
        prevBlockTail.next = reverse(blockStart);                    // kth is now the first node of the block
        blockStart.next = nextBlockStart;                            // the old first node is now the block's tail
        prevBlockTail = blockStart;
    }
    return dummy.next;
}

static ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

Dry run on 1 -> 2 -> 3 -> 4 -> 5, k = 2:

prevBlockTail kth block after splice
dummy 2 1 -> 2 dummy -> 2 -> 1 -> 3 -> 4 -> 5
1 4 3 -> 4 dummy -> 2 -> 1 -> 4 -> 3 -> 5
3 null   stop

Result: 2 -> 1 -> 4 -> 3 -> 5.

Complexity. Time O(n): the walk to kth and the reversal together touch each node of every block twice, and the walk that fails on the final short block touches at most k - 1 nodes. Space O(1): a fixed number of pointers.

Why cut the block off before reversing? The reverse helper runs until it sees null. Without kth.next = null it would reverse the entire rest of the list. Cutting first lets us reuse the plain whole-list reversal unchanged, and nextBlockStart remembers where to reattach.

Edge cases and pitfalls