Reverse Nodes in k-Group

You are given the head of a singly linked list and a positive integer k that is at most the length of the list. Split the list, from the front, into consecutive blocks of exactly k nodes. Reverse the order of the nodes inside every full block. If fewer than k nodes remain at the end, leave that tail exactly as it is.

Return the head of the rearranged list. You must relink the nodes themselves; changing the values stored in them is not allowed.

In the tests the list is written as an array of node values, front to back.

Example 1

Example 2

Example 3

Constraints

• The number of nodes is n, with 1 <= k <= n <= 5000
• -1000 <= Node.val <= 1000
• Aim for O(1) extra memory besides the list itself.

Pattern Path · Linked Lists · problem 79 of 169

Start simple

Copy the values into an array, reverse each full chunk, and write the values back: O(n) time but O(n) extra space, and it edits values rather than relinking nodes.

The key idea

The work is ordinary in-place list reversal, applied block by block. The difficulty is purely in the bookkeeping at the block boundaries, so it helps to name the four nodes that matter: group_prev (just before the block), the block's first node, its k-th node, and group_next (just after it).

Start with a dummy node in front of the head so that the first block has a group_prev like every other block. Then repeat:

• Walk k steps from group_prev. If the list ends first, the remaining tail is shorter than k; return dummy.next.
• Reverse the nodes from the first node up to the k-th, starting the running prev pointer at group_next. That way the old first node ends up pointing to the rest of the list automatically.
• Link group_prev.next to the old k-th node (the new front), and move group_prev to the old first node, which is now the block's last node.

Every node is visited a constant number of times (once while checking, once while reversing), so the total is linear, and only a few pointers are used.

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def reverseKGroup(self, head, k):
        dummy = ListNode(0, head)
        group_prev = dummy  # the node just before the current group

        while True:
            # Walk to the k-th node of this group; stop if fewer than k remain.
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if kth is None:
                    return dummy.next
            group_next = kth.next

            # Reverse the group. Starting `prev` at group_next makes the
            # old first node point past the group when we are done.
            prev, cur = group_next, group_prev.next
            while cur is not group_next:
                nxt = cur.next
                cur.next = prev
                prev = cur
                cur = nxt

            # kth is the new first node; the old first node is the new last.
            old_first = group_prev.next
            group_prev.next = kth
            group_prev = old_first

JavaScript

var reverseKGroup = function(head, k) {
  const dummy = new ListNode(0, head);
  let groupPrev = dummy; // the node just before the current group

  while (true) {
    // Walk to the k-th node of this group; stop if fewer than k remain.
    let kth = groupPrev;
    for (let step = 0; step < k; step++) {
      kth = kth.next;
      if (kth === null) return dummy.next;
    }
    const groupNext = kth.next;

    // Reverse the group. Starting prev at groupNext makes the
    // old first node point past the group when we are done.
    let prev = groupNext;
    let cur = groupPrev.next;
    while (cur !== groupNext) {
      const nxt = cur.next;
      cur.next = prev;
      prev = cur;
      cur = nxt;
    }

    // kth is the new first node; the old first node is the new last.
    const oldFirst = groupPrev.next;
    groupPrev.next = kth;
    groupPrev = oldFirst;
  }
};

What the interviewer is checking

The interviewer is checking whether you can manipulate pointers precisely under pressure: reversing in place, reconnecting block boundaries, and not losing the rest of the list.

Mistakes to avoid

• Reversing the final partial block; it must stay in its original order.
• Losing the link from the previous block to the new front of the current block.
• Advancing group_prev to the wrong node: it should become the old first node of the block just reversed.
• Special-casing the first block instead of using a dummy node, which leads to duplicated, bug-prone code.

Follow-ups to expect

• What if the leftover tail should also be reversed? (Drop the completeness check.)
• Can you write it recursively, and what does that cost? (O(n/k) stack frames.)
• How would you reverse blocks counted from the end of the list? (Skip n mod k nodes first.)

In real software

Reordering fixed-size chunks in place shows up in byte-order swapping of packed data and in reordering linked buffers in network stacks, where allocating new nodes is too expensive.

Practice next