4.9.11 — Reverse Nodes in K-Group

LeetCode 25 · Hard

The problem

Reverse the list in groups of k. If the last group has fewer than k nodes, leave it alone. You must move nodes, not values.

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

The Plain-English Breakdown

You are given a linked list. Instead of reversing the whole thing, you have to reverse it in chunks of size k. If you get to the end of the list and the final chunk has fewer than k nodes, you must leave that final chunk exactly as it is (not reversed).

Constraints to note:

• k is between 1 and the length of the list.
• You must use O(1) extra memory space.

Brute Force Analysis

A brute force approach that violates the constraints would be to traverse the linked list, extract all node values into an array, reverse the values in the array in chunks of k using standard array slicing, and then build a brand new linked list from those values.

• Why it fails: It uses O(N) extra memory for the array, explicitly violating the O(1) space requirement. It also violates the core spirit of linked list pointer manipulation problems. You must rewire the existing nodes.

The pattern

You already know how to reverse a list (4.9.1). The new work is entirely in the stitching: after reversing a block, its ends have swapped, and you have to reconnect it to the block before and the block after.

For each group, four nodes matter:

        groupPrev            groupNext
            |                    |
   … → [ A → B → C ] → D → …
            ^       ^
          first    last  (of the group)

after reversing the group:

   … → [ C → B → A ] → D → …

• groupPrev — the last node of the previous group. Its next must end up pointing at C, the new first node.
• A — the group's original first node, which becomes its last. Its next must point at D.

Two connections per group. Get those right and the problem is done.

ELI5 Analogy: Imagine taking a long necklace and painting marks on it every k beads. You snip the necklace at a mark, take that chunk of k beads, flip it backward, and tie it back in. To tie it back in successfully, you need to hold on to the bead just before the snip (groupPrev) and the bead just after the snip (groupNext). If you don't hold those ends while you flip the middle, the rest of the necklace falls on the floor and is lost forever!

Code Walkthrough

1. The Setup: We use a dummy node pointing to head. group_prev starts at dummy. This is the node immediately before the group we are about to reverse.
2. The Verification Walk: Inside our infinite while True loop, we create a kth pointer. We walk it forward k steps. If we hit null before finishing k steps, the group is incomplete! We immediately return dummy.next.
3. The Boundaries: If we successfully found the kth node, the node after it is group_next = kth.next. We now know our boundaries.
4. The Reversal: We set prev = group_next and curr = group_prev.next. We do a standard linked list reversal (curr.next = prev, etc.) in a while loop, but instead of stopping at null, we stop when curr hits group_next.
5. The Stitch: After reversal, the group's original first node (group_prev.next) is now at the end of the reversed chunk. We save it as new_group_prev. We then connect our before-snip node (group_prev) to the new head of the chunk (kth). Finally, we move group_prev forward to prepare for the next round.

The other half: knowing when to stop

Before reversing a group you must confirm there are k more nodes, because an incomplete final group is left untouched. So each round starts by walking k steps forward to find groupNext. If you fall off the end first, stop.

That walk is not wasted work — it is also how you find groupNext, which you need anyway.

The solution

Python

class Solution:
    def reverseKGroup(self, head, k: int):
        dummy = ListNode(0, head)
        group_prev = dummy

        while True:
            # 1. is there a full group left? walk k steps
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next          # incomplete group — leave it
            group_next = kth.next

            # 2. reverse the group, ending it at group_next
            prev, curr = group_next, group_prev.next
            while curr is not group_next:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt

            # 3. stitch: group_prev.next was the group's first node,
            #    which is now its last — so it becomes the next group_prev
            new_group_prev = group_prev.next
            group_prev.next = kth              # kth is the new first node
            group_prev = new_group_prev

TypeScript

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let groupPrev: ListNode = dummy;

  while (true) {
    let kth: ListNode | null = groupPrev;
    for (let i = 0; i < k; i++) {
      kth = kth!.next;
      if (!kth) return dummy.next;
    }
    const groupNext = kth.next;

    let prev = groupNext, curr = groupPrev.next;
    while (curr !== groupNext) {
      const nxt = curr!.next;
      curr!.next = prev;
      prev = curr;
      curr = nxt;
    }

    const newGroupPrev = groupPrev.next!;
    groupPrev.next = kth;
    groupPrev = newGroupPrev;
  }
}

Three details do all the work.

prev starts at group_next, not at None. In the plain reversal, the last node ends up pointing at null because the list ends there. Here the group is in the middle, so its last node must point at whatever follows the group. Seeding prev with group_next makes the standard reversal loop produce that automatically — no fix-up afterwards.

The loop condition is curr is not group_next. It reverses exactly the nodes of this group and stops at the boundary.

new_group_prev is captured before the stitch. group_prev.next currently points at the group's original first node, which after reversal is its last node — and that is exactly the group_prev for the next round. Read it before overwriting group_prev.next, or it is gone.

The dummy head means the very first group needs no special case, even though reversing it changes the head of the whole list.

Trace on 1 → 2 → 3 → 4 → 5, k = 2

Round 1. group_prev = dummy. Walk 2 steps: kth = 2. group_next = 3.

Reverse 1 → 2 with prev seeded to node 3: node 1 points to 3, node 2 points to 1.

Stitch: new_group_prev = node 1. dummy.next = node 2. So the list is 2 → 1 → 3 → 4 → 5, and group_prev = node 1.

Round 2. Walk 2 steps from node 1: kth = 4. group_next = 5.

Reverse 3 → 4 with prev = node 5: node 3 points to 5, node 4 points to 3.

Stitch: new_group_prev = node 3. node1.next = node 4. List is 2 → 1 → 4 → 3 → 5, group_prev = node 3.

Round 3. Walk 2 steps from node 3: first step reaches node 5, second step is null → return.

Final: 2 → 1 → 4 → 3 → 5. ✓

Complexity

O(n) time. Each node is visited twice — once by the counting walk, once by the reversal — which is 2n, so still linear.

O(1) space. The recursive version is O(n/k) stack space and is easier to write, but it is not constant space and the problem's follow-up asks for constant.

Derivation:

• Time Complexity: O(N). To process a group of size k, we first walk k steps to verify its length and find the kth node. Then we walk those same k steps again to perform the actual reversal. Each node is visited exactly twice. 2N \rightarrow O(N).
• Space Complexity: O(1). We only maintain a fixed number of pointers (dummy, group_prev, kth, group_next, prev, curr, nxt). No recursion is used, and no arrays are created. Memory usage is constant regardless of list length.

Where this goes next

• Swap Nodes in Pairs (LeetCode 24) — this problem with k = 2. If you can write this one, that one is free.
• Reverse Linked List II — reverse a single named range. Same stitching, one group.
• Rotate List — connect the tail to the head to make a ring, then cut it in the right place.

The rule: when reversing part of a list, seed prev with whatever should follow the reversed section, and capture the new boundary node before you overwrite the pointer to it.

What the interviewer will push on

"Why does prev start at group_next?" So the group's last node points at the rest of the list automatically, instead of at null.

"How do you know a full group remains?" Walk k steps first, returning if you hit null. The same walk finds group_next.

"Why do you capture new_group_prev before stitching?" Because the stitch overwrites the pointer you would need to find it.

"Can you do it recursively?" Yes, and it is shorter, but it uses O(n/k) stack. The follow-up asks for O(1).

"What if k is 1, or larger than the list?" k = 1 reverses nothing and the list is unchanged. k larger than the list means the first group is already incomplete, so nothing happens and the original head is returned.

One thing to volunteer: draw the four pointers before writing code, and name them out loud. This problem is not conceptually hard — it is bookkeeping — and the people who fail it are the ones who started typing without the picture.

Next: 4.9.12 LFU Cache — beyond the NeetCode 150, the follow-up interviewers ask right after LRU: evict by use count, with recency breaking ties, still in O(1).