Reverse in groups of k

Why this matters

Reversing a whole list is a single job. Reversing a list in blocks is the same job repeated, with one extra task: each reversed block must join the blocks before and after it. Most mistakes in this problem are not in the reversal itself. They come from losing a pointer at a join.

This problem also combines three skills from earlier lessons in this module. It uses the reversal loop from the reverse lesson, a pointer that walks ahead a fixed number of steps, and a placeholder node in front of the list. The placeholder is called a dummy node. It is a node that holds no real value and sits before the first real node, so the first block needs no special case. The sentinel lesson covers the same idea for doubly linked lists.

By the end of this lesson you will write a function that takes a list and a number k, reverses each full block of k nodes, and leaves any short block at the end as it was. It runs in O(n) time, meaning the time grows in step with the number of nodes, and it uses O(1) extra space, meaning only a fixed number of pointers beyond the list itself.

The idea in plain words

Take the list 1, 2, 3, 4, 5, 6, 7 and set k to 3. Cut the list into blocks of three nodes from the front.

[1 2 3] [4 5 6] [7]

The first two blocks are full, so each one is reversed. The last block has one node, which is fewer than 3, so it is left alone.

[3 2 1] [6 5 4] [7]

Join the blocks in the same order as before, and the result is 3, 2, 1, 6, 5, 4, 7. The blocks keep their order. Only the inside of each full block is turned around.

Every full block needs the same three steps.

1. Find the last node of the block. Walk k steps ahead from the node just before the block. If the walk runs off the end of the list, the block is short.
2. Reverse the nodes of the block, and keep the node after the block so the list is not broken.
3. Reconnect. The node just before the block must point to the block's new first node, which was its last node before the reversal. The block's old first node is now the block's last node, so it becomes the node just before the next block.

The next sections build the function one step at a time, using the list 1 to 7 with k set to 3.

Step 1: finding the end of a block

The first helper is a loop that walks k steps from a starting node. The starting node is the one just before the block, called group_prev. Its next pointer leads to the first node of the block.

Node* kth = group_prev;
for (int i = 0; i < k && kth != nullptr; ++i) {
    kth = kth->next;
}

The loop counts k steps. It stops early if kth becomes nullptr, which means the list ended before k steps. After the loop, kth is either the last node of the block, or nullptr when the block is short.

The table shows the walk for the first block of the list 1 to 7, where group_prev is the dummy node in front of node 1.

The walk runs before any arrow changes. A short block is found without touching the list, so nothing has to be undone. The alternative, reversing first and then discovering that the block is short, would leave the list in a state that needs repair.

For the second block, the walk starts from node 1, which is now the node before block two. It moves through 4, 5 and 6, and stops at 6. For the last block, the walk starts from node 4 and goes through 7, then reaches nullptr after node 7. The walk ran out, so the block is short and no reversal is done.

Step 2: reversing one block

Once kth is known, the block runs from the node after group_prev up to kth. Two pointers mark the edges of the block.

Node* group_next = kth->next;   // the node just after the block
Node* old_first = group_prev->next;  // the block's first node, before the reversal

The reversal loop is the one from the reverse lesson, with two changes. It starts prev at group_next, not at nullptr. It stops when cur reaches group_next, not when it reaches nullptr.

Node* prev = group_next;
Node* cur = old_first;
while (cur != group_next) {
    Node* nxt = cur->next;
    cur->next = prev;
    prev = cur;
    cur = nxt;
}

Starting prev at group_next matters. The first node of the block is old_first. After the reversal it becomes the last node of the block, and its next must point at the node after the block. The first pass of the loop sets old_first->next to prev, which is group_next. A reversal started at nullptr would make the block's last node point to nothing, and the rest of the list would be lost.

The loop runs once for each node in the block. For block one of the list 1 to 7, the loop turns the arrows of nodes 1, 2 and 3. The table shows each pass.

When the loop ends, prev points at node 3, the new first node of the block. The arrows read 3 to 2 to 1 to 4, where 4 is group_next.

Step 3: reconnecting and moving on

The reversed block still has to be attached to the list. The node before the block must point to its new first node, which is kth.

group_prev->next = kth;

Then old_first is the last node of the block, and the next block starts after it. The function returns old_first so the caller can use it as the new group_prev.

Trace block one of the list 1 to 7. Before the step, the dummy points to 1. After the step, the dummy points to 3, 3 points to 2, 2 points to 1, and 1 points to 4. The block is joined to the rest of the list, and group_prev moves to node 1.

The complete function

Here is the full program. The function reverse_in_groups loops over the blocks, calling reverse_one_group until it reports a short block. The program runs the function on several inputs and prints each result. The tests include an empty list, a block size larger than the list, and a block size of 1.

The program was compiled with g++ -std=c++20 -Wall -Wextra -g -fsanitize=address,undefined and run. The sanitizers reported no memory errors and no leaked nodes. Its output was:

k=3  before: 1 2 3 4 5 6 7 
k=3  after:  3 2 1 6 5 4 7 
k=2  before: 1 2 3 4 
k=2  after:  2 1 4 3 
k=3  before: 1 2 3 4 5 6 7 8 
k=3  after:  3 2 1 6 5 4 7 8 
k=1  before: 1 2 3 
k=1  after:  1 2 3 
k=10  before: 1 2 3 
k=10  after:  1 2 3 
k=2  before: 
k=2  after:  

The k=1 case shows that a block of one node reverses to itself, so the list is unchanged. The k=10 case has a single short block, which is left alone. The empty list is returned as it is, because the walk in the first block finds no node.

More worked examples

The first example used 7 nodes. Here is a second example with 8 nodes and k set to 3, traced one round at a time. Each round is one call to reverse_one_group. The table shows the node that group_prev points to at the start of the round, and what the round does.

In round 3 the walk from node 4 goes through 7 and 8, then reaches nullptr. The block is short, so reverse_one_group returns nullptr, and the loop in reverse_in_groups ends. The final list is 3, 2, 1, 6, 5, 4, 7, 8.

A third example checks the reasoning on a list where every block is full. The list 1, 2, 3, 4 with k set to 2 has two blocks, [1 2] and [3 4]. Each one is reversed, and the result is 2, 1, 4, 3. The output printed by the complete program above matches this result.

A fourth example is a block size larger than the list. With 3 nodes and k set to 10, the first walk runs past the end of the list in round one, so no block is reversed. The output is the same as the input. The program does not need a special check for this case, because the walk already reports a short block.

Why the dummy node helps

The first block has no node before it, so group_prev for that block would be nullptr, and the code would need a separate branch. The dummy node avoids that branch. It sits in front of the list, so group_prev always points to a real node, and the join step group_prev->next = kth works the same way for every block.

The dummy node is a local variable, not a heap node. Its address is used only inside the function, and the function returns dummy.next, which is the real first node. The dummy is never freed, and it must not be, because it was not allocated with new.

Checking the function against a simple version

A check against a second, simpler version finds mistakes that a few hand-picked examples miss. The simpler version copies the values into a std::vector, reverses each full block with std::reverse, and returns the result. It is slower and uses more memory, which is why it is only used for testing.

std::vector<int> reference_groups(std::vector<int> values, std::size_t k) {
    for (std::size_t start = 0; start + k <= values.size(); start += k) {
        std::reverse(values.begin() + start, values.begin() + start + k);
    }
    return values;
}
 
std::vector<int> to_vector(const Node* head) {
    std::vector<int> values;
    for (const Node* cur = head; cur != nullptr; cur = cur->next) {
        values.push_back(cur->value);
    }
    return values;
}

The test builds lists of length 0 to 12, with values 1 to n, and tries every k from 1 to 13. For each pair it compares the list from reverse_in_groups with the vector from reference_groups. Add the two functions above to the complete program, and use this main in place of the earlier one. The headers <algorithm>, <cstddef> and <numeric> are needed for std::reverse, std::size_t and std::iota.

int main() {
    int checks = 0;
    for (std::size_t n = 0; n <= 12; ++n) {
        for (int k = 1; k <= 13; ++k) {
            std::vector<int> values(n);
            std::iota(values.begin(), values.end(), 1);
            Node* list = build_list(values);
            list = reverse_in_groups(list, k);
            if (to_vector(list) != reference_groups(values, static_cast<std::size_t>(k))) {
                std::cout << "mismatch for n=" << n << " k=" << k << '\n';
                return 1;
            }
            free_list(list);
            ++checks;
        }
    }
    std::cout << "checks passed: " << checks << '\n';
    return 0;
}

The program was built with the same flags as before, plus the sanitizers, and printed:

checks passed: 169

The count is 13 lengths times 13 block sizes. The sanitizers reported no errors and no leaked nodes.

Common mistakes

Starting the reversal at nullptr

If the reversal starts with Node* prev = nullptr;, the last node of each block points to nullptr, and everything after the block is lost. Running the program with this change on the list 1 to 7 and k set to 3 printed:

k=3  before: 1 2 3 4 5 6 7 
k=3  after:  3 2 1 

The nodes 4 to 7 are still in memory, but no pointer leads to them, so they are leaked. The fix is to start prev at group_next.

Not moving group_prev forward

After a block is reversed, the next round must start from the node that is now the end of the block. A version of the loop that forgets this step keeps group_prev at the dummy node. The second round then rewires from the wrong place, and the list can end up pointing back into itself. In one test run of that version, the loop in reverse_in_groups never ended, and the program was stopped by the time limit. A loop that never ends is a sign that a pointer was not moved forward.

Passing a k of zero or less

A value of k of 0 makes the walk take no steps. Then kth equals group_prev, and the join step sets group_prev->next to group_prev itself. The list then loops back on itself. In a test run of the function without the guard, the list printed the same leftover number forever (the dummy node was a local variable, so its memory was no longer valid), and the program had to be stopped by the time limit. The guard at the top of reverse_in_groups stops this. The guard throws an exception. If the caller does not catch it, the program ends with this output:

terminate called after throwing an instance of 'std::invalid_argument'
  what():  k must be at least 1

The exit code was 134, which is the code for a program that stops because of an abort.

Returning head instead of dummy.next

The head of the list can change during the work, because the first block is reversed. The function must return dummy.next, not the original head argument. Returning the original head gives a pointer to the old first node, which is now the last node of the first block.

Practice

Exercise 1

Trace reverse_in_groups by hand on the list 1, 2, 3, 4, 5 with k set to 2. Write the list after each round.

Show the answer

Round 1 reverses [1 2], giving 2, 1, 3, 4, 5. Round 2 reverses [3 4], giving 2, 1, 4, 3, 5. Round 3 finds the block [5] as short, so the list stays as it is. The final list is 2, 1, 4, 3, 5.

Exercise 2

Write count_full_groups, which takes a list and a number k and returns how many full blocks of k nodes the list has. The function must not change the list.

Show the answer

int count_full_groups(const Node* head, int k) {
    int count = 0;
    while (head != nullptr) {
        const Node* probe = head;
        int seen = 0;
        while (probe != nullptr && seen < k) {
            probe = probe->next;
            ++seen;
        }
        if (seen < k) {
            break;
        }
        ++count;
        head = probe;
    }
    return count;
}

The inner loop walks ahead k nodes from the start of a block. If the walk ends early, the block is short and the outer loop stops. Otherwise the count goes up, and head moves to the node after the block. The list has 2 full blocks of 3 for the list 1 to 7, and 3 full blocks of 2 for the same list. The program that tested this function printed full groups of 3: 2 and full groups of 2: 3.

Exercise 3

Explain in plain words why reverse_one_group sets prev to group_next at the start, not to nullptr.

Show the answer

The first node of the block becomes the last node after the reversal. It must point to the node that comes after the block. Setting prev to group_next makes the first step of the loop set that pointer correctly. Setting prev to nullptr would cut the list at the end of the block.

Exercise 4

Predict what the program prints for the list 1 to 5 with k set to 5, and then for k set to 6.

Show the answer

With k set to 5, the single block is full, so it is reversed. The output is 5 4 3 2 1. With k set to 6, the block is short, so nothing changes. The output is 1 2 3 4 5.

Exercise 5

Compare the cost of this lesson's method with a method that copies the values into a std::vector, reverses each block of values, and writes the values back into the nodes. Give the time and extra space for each method.

Show the answer

The pointer method takes O(n) time and O(1) extra space, because it only moves pointers and uses a fixed number of local variables. The vector method also takes O(n) time, since it visits every node a fixed number of times. It takes O(n) extra space, because the vector holds one value for each node. The pointer method is the one this lesson practises, because the nodes are moved rather than copied.

Summary

• Reversing in groups means reversing each full block and leaving a short last block alone.
• A walk of k steps finds the end of a block, and a block is short when the walk runs off the list.
• The reversal of one block starts prev at the node after the block, so the block joins the rest of the list.
• After each block, group_prev moves to the block's old first node, which is now its last node.
• A dummy node in front of the list removes the special case for the first block, and the function returns dummy.next.