SyntaxPilot
Courses/DSA and Coding Problems/Lesson 24
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 24 of 90

Reverse nodes in k-group (hard)

queued

These are the notes for DSA episode 24, the last hard problem of the linked list block. Reverse a linked list k nodes at a time, leave a short last group alone, and do it in place with O(1) extra memory. The obvious way treats the list like an array: get(i), get(j), swap values. Every get walks from the head, so it is O(n²/k) and times out on 2 lakh nodes, and it swaps values, which the problem forbids. The fix reuses episode 21's prev / curr / next on one group at a time, with a dummy node and two bookmarks, groupPrev and groupNext: O(n) time, O(1) space. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

A train with coaches 1 to 5 reaches a yard whose turntable can only turn 3 coaches at a time (a set of coaches moved together is a rake). The yard splits the train into rakes [1 2 3] [4 5], turns each full rake ([3 2 1]), and hooks everything back together. The last rake has only 2 coaches, so it isn't turned: the train becomes 3 2 1 4 5.

In the yard In the code
A rake of k coaches A group of k nodes
Turning a rake on the turntable Reversing the group's links
The coach just before the rake groupPrev
The coach just after the rake groupNext
The last coach of the rake kth
A short last rake fewer than k nodes left: unchanged

Problem statement

Given the head of a linked list and an integer k, reverse the nodes k at a time and return the new head. If fewer than k nodes remain at the end, leave them in order. Change links, not values, and use O(1) extra memory.

1->2->3->4->5, k = 2   →   2->1->4->3->5
1->2->3->4->5, k = 3   →   3->2->1->4->5

Edge cases: k = 1 (unchanged), k = n (fully reversed), k > n (unchanged), an empty list.

Brute force: pretend it's an array

Count the nodes, then reverse each full group like an array: swap the two ends, move inwards. A list has no index, so get(head, i) walks i steps.

    static Node get(Node head, int i) {
        while (i-- > 0) head = head.next;
        return head;
    }
    static Node bruteK(Node head, int k) {
        int n = 0;
        for (Node c = head; c != null; c = c.next) n++;
        for (int s = 0; s + k <= n; s += k)
            for (int i = s, j = s + k - 1; i < j; i++, j--) {
                Node a = get(head, i), b = get(head, j);
                int t = a.val; a.val = b.val; b.val = t;
            }
        return head;
    }

With k = 2 and k = 3 on 1..5 it printed 2 -> 1 -> 4 -> 3 -> 5 -> null and 3 -> 2 -> 1 -> 4 -> 5 -> null. Correct answers, but it swaps values.

The big input: 2 lakh nodes

A list 1..200000 with k = 3: Time Limit Exceeded.

Why the brute force fails

Every swap calls get twice, and each get walks from the head (up to n steps). With n/k groups that's about n²/k hops (≈ n²/3 for k = 3).

Nodes Hops (about n²/3)
1,000 3 lakh
20,000 13 crore
2,00,000 1.3 × 10¹⁰: TLE

And it breaks the rule: it moves values, not nodes.

The key insight: one group at a time, with bookmarks

We already reverse links in one walk (episode 21). Do it for one group, then hook the group back in. Before touching a group, mark both sides:

  1. From groupPrev, walk k steps: that node is kth. If you hit null first, fewer than k remain: stop.
  2. groupNext = kth.next. Reverse the group with prev / curr / next, but prev starts at groupNext, not null, so the group's new tail is already hooked to the rest.
  3. groupPrev.next = kth: the group's new front. The group's old first node is now its tail.
  4. groupPrev = that old first node. Repeat.

A dummy node before the head gives even the first group a groupPrev, so changing the head isn't a special case. Return dummy.next.

Trace with k = 3 on D -> 1 -> 2 -> 3 -> 4 -> 5:

Step What happens List (following arrows from D)
1 groupPrev = D; walk 3: kth = 3, groupNext = 4 D 1 2 3 4 5
2 reverse 1..3 with prev = 4: 1→4, 2→1, 3→2 D 1 4 5 (D still points to 1)
3 D.next = 3; first = 1 D 3 2 1 4 5
4 groupPrev = 1; walk 3: 4, 5, null → stop D 3 2 1 4 5
end return D.next 3 2 1 4 5

The optimal solution in Java

public class Main {
    static class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }
    static Node build(int... a) {
        Node head = null;
        for (int i = a.length - 1; i >= 0; i--) {
            Node n = new Node(a[i]);
            n.next = head;
            head = n;
        }
        return head;
    }
    static String show(Node h) {
        StringBuilder sb = new StringBuilder();
        for (; h != null; h = h.next) sb.append(h.val).append(" -> ");
        return sb.append("null").toString();
    }
    static Node reverseKGroup(Node head, int k) {
        Node dummy = new Node(0);
        dummy.next = head;
        Node groupPrev = dummy;
        while (true) {
            Node kth = groupPrev;
            for (int i = 0; i < k && kth != null; i++) kth = kth.next;
            if (kth == null) break;
            Node groupNext = kth.next;
            Node prev = groupNext, curr = groupPrev.next;
            while (curr != groupNext) {
                Node next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            Node first = groupPrev.next;
            groupPrev.next = kth;
            groupPrev = first;
        }
        return dummy.next;
    }
    public static void main(String[] args) {
        System.out.println(show(reverseKGroup(build(1, 2, 3, 4, 5), 2)));
        System.out.println(show(reverseKGroup(build(1, 2, 3, 4, 5), 3)));
        System.out.println(show(reverseKGroup(build(1, 2, 3, 4, 5), 1)));
        System.out.println(show(reverseKGroup(build(1, 2, 3, 4, 5), 5)));
        System.out.println(show(reverseKGroup(build(1, 2, 3, 4, 5), 6)));
        System.out.println(show(reverseKGroup(null, 2)));
    }
}

Output:

2 -> 1 -> 4 -> 3 -> 5 -> null
3 -> 2 -> 1 -> 4 -> 5 -> null
1 -> 2 -> 3 -> 4 -> 5 -> null
5 -> 4 -> 3 -> 2 -> 1 -> null
1 -> 2 -> 3 -> 4 -> 5 -> null
null

On 2 lakh nodes with k = 3 it printed starts 3 2 1, 36 ms. Each node is visited about twice: once while counting k ahead, once while reversing.

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

Node* build(const vector<int>& a) {
    Node* head = nullptr;
    for (int i = (int)a.size() - 1; i >= 0; i--) { Node* n = new Node(a[i]); n->next = head; head = n; }
    return head;
}
string show(Node* h) { string s; for (; h; h = h->next) s += to_string(h->val) + " -> "; return s + "null"; }

Node* reverseKGroup(Node* head, int k) {
    Node dummy(0);
    dummy.next = head;
    Node* groupPrev = &dummy;
    while (true) {
        Node* kth = groupPrev;
        for (int i = 0; i < k && kth; i++) kth = kth->next;
        if (!kth) break;
        Node* groupNext = kth->next;
        Node *prev = groupNext, *curr = groupPrev->next;
        while (curr != groupNext) {
            Node* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        Node* first = groupPrev->next;
        groupPrev->next = kth;
        groupPrev = first;
    }
    return dummy.next;
}

int main() {
    for (int k : {2, 3, 1, 5, 6}) cout << show(reverseKGroup(build({1, 2, 3, 4, 5}), k)) << "\n";
}

Output: the first five lines of the Java output.

The same solution in Python

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def build(*a):
    head = None
    for x in reversed(a):
        head = Node(x, head)
    return head

def show(h):
    out = []
    while h:
        out.append(str(h.val)); h = h.next
    return " -> ".join(out + ["null"])

def reverse_k_group(head, k):
    dummy = Node(0, head)
    group_prev = dummy
    while True:
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if kth is None:
                return dummy.next          # fewer than k left: leave them
        group_next = kth.next
        prev, curr = group_next, group_prev.next
        while curr is not group_next:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        first = group_prev.next
        group_prev.next = kth
        group_prev = first

for k in (2, 3, 1, 5, 6):
    print(show(reverse_k_group(build(1, 2, 3, 4, 5), k)))
print(show(reverse_k_group(None, 2)))

Output: the same six lines as Java.

Three real bugs

Bug 1: Node prev = null inside the group

Copying episode 21 exactly. With k = 3: 3 -> 2 -> 1 -> null. Node 1, the group's new tail, points to null, so 4 and 5 are cut off. Fix: prev = groupNext.

Bug 2: forgetting groupPrev = first

Time Limit Exceeded. groupPrev stays on the dummy, so the loop finds the same first group again and flips it back, forever.

Bug 3: return head;

With k = 3: 1 -> 4 -> 5 -> null. head still points at node 1, which is now in the middle (the first group's tail). Fix: return dummy.next.

And if you delete the if (kth == null) break;, Java refuses to compile:

Main.java:40: error: unreachable statement
        return dummy.next;
        ^
1 error

while (true) with no break can never finish, so the return after it can never run.

Complexity

Approach Time Extra space 2 lakh nodes, k = 3
get(i) + swap values O(n²/k) O(1), but swaps values Time Limit Exceeded
Copy values to an array, reverse blocks O(n) O(n), swaps values not allowed
Dummy + groupPrev + reverse O(n) O(1) 36 ms
Recursive group reversal O(n) O(n/k) call stack fine for moderate n

Common mistakes

Mistake What you see Why Fix
Node prev = null inside a group 3 -> 2 -> 1 -> null the group's tail points to null prev = groupNext
No groupPrev = first Time Limit Exceeded the same group flips back and forth move groupPrev to the old first node
return head; 1 -> 4 -> 5 -> null (k = 3) the old head is now inside the list return dummy.next
No if (kth == null) break; error: unreachable statement while (true) never ends break when no full group is left
Reversing the short last group 3 -> 2 -> 1 -> 5 -> 4 (k = 3) didn't check the group is full count k ahead before reversing
Treating the list like an array TLE get(i) is O(n) walk once with pointers

Mini project: a bus seating chart

A bus fills seats in rows of k from the front; for the return trip each full row is reversed (window seats swap sides), and a partly filled last row keeps its order. Store passenger ids in a list and print the return-trip order with reverseKGroup(ids, k): for ids 1..8 and k = 3 it is 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8 -> null. Extension: also reverse the last partial row (practice 1).

Practice

  1. Reverse in groups of k, and also the last short group.
Solution

Same loop, but kth stops at the last real node instead of requiring a full group.

    static Node reverseAllGroups(Node head, int k) {
        Node dummy = new Node(0);
        dummy.next = head;
        Node groupPrev = dummy;
        while (groupPrev.next != null) {
            Node kth = groupPrev;
            for (int i = 0; i < k && kth.next != null; i++) kth = kth.next;
            Node groupNext = kth.next;
            Node prev = groupNext, curr = groupPrev.next;
            while (curr != groupNext) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }
            Node first = groupPrev.next;
            groupPrev.next = kth;
            groupPrev = first;
        }
        return dummy.next;
    }

1..5, k = 3 → 3 -> 2 -> 1 -> 5 -> 4 -> null.

  1. Swap nodes in pairs (k = 2) without the general code.
Solution
    static Node swapPairs(Node head) {
        Node dummy = new Node(0);
        dummy.next = head;
        Node prev = dummy;
        while (prev.next != null && prev.next.next != null) {
            Node a = prev.next, b = a.next;
            a.next = b.next;
            b.next = a;
            prev.next = b;
            prev = a;
        }
        return dummy.next;
    }

1..5 → 2 -> 1 -> 4 -> 3 -> 5 -> null.

  1. The recursive version.
Solution

Check a full group exists, reverse the rest recursively, then reverse this group with prev starting at the reversed rest.

    static Node reverseKRec(Node head, int k) {
        Node kth = head;
        for (int i = 0; i < k; i++) {
            if (kth == null) return head;
            kth = kth.next;
        }
        Node prev = reverseKRec(kth, k), curr = head;
        while (curr != kth) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }
        return prev;
    }

1..8, k = 3 → 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8 -> null. Uses O(n/k) stack.

  1. Reverse every alternate group of k (reverse, skip, reverse, skip ...): after re-hooking a group, walk groupPrev forward k more nodes before the next reversal.

Quick quiz

show(reverseKGroup(build(1, 2, 3, 4, 5, 6, 7, 8), 3))
  • 3->2->1->6->5->4->8->7->null
  • 3->2->1->6->5->4->7->8->null
  • 8->7->6->5->4->3->2->1->null
  • 1->2->3->4->5->6->7->8->null
Answer

3->2->1->6->5->4->7->8->null. Two full groups are reversed; 7 and 8 are fewer than k, so they stay in order. (Real output: 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8 -> null.)

Interview questions

  1. Reverse nodes in k-group in O(1) space. Dummy node; for each group count k ahead, reverse with prev = groupNext, re-hook groupPrev.next = kth, move groupPrev to the old first node.
  2. Why does prev start at groupNext? So the reversed group's new tail already points to the rest of the list.
  3. Why a dummy node? The first group changes the head; the dummy gives it a groupPrev like every other group.
  4. Time complexity? O(n): each node is counted once and reversed once.
  5. What happens with the last short group? It is left in order (unless the variant asks otherwise).
  6. Iterative vs recursive? Same O(n) time; recursion uses O(n/k) stack frames.
  7. How is this related to "reverse a linked list"? It's the same three-pointer loop applied to a bounded section, plus re-linking the boundaries.
  8. Why not swap values? The problem forbids it, and real nodes may carry large or immutable data.

Glossary

Term Meaning
Group (of k) k consecutive nodes reversed together
groupPrev The node just before the current group (initially the dummy)
kth The last node of the current group; after reversal, its new front
groupNext The node just after the current group
Dummy node A fake node before the head so the first group isn't a special case
In place Rearranging the existing nodes without building new ones
get(i) on a list Walking i steps from the head: O(i)
prev / curr / next The three pointers of the reversal loop (episode 21)
Unreachable statement A Java compile error for code that can never run
O(n²/k) Work that grows with the square of n, divided by k
O(1) space Extra memory that doesn't grow with the input
Time Limit Exceeded (TLE) Too slow for the judge's limit (8 s in the SyntaxPilot compiler)

Summary

  • get(i) on a linked list is O(n), so "pretend it's an array" is O(n²/k) and times out; it also swaps values.
  • Use a dummy node and process one group at a time: count k ahead (stop if short), reverse with prev = groupNext, groupPrev.next = kth, groupPrev = first.
  • O(n) time, O(1) extra space; return dummy.next.

Next episode: LRU cache: hash map + doubly linked list.