Reverse in groups of k in Python

Why this matters

Reversing a whole list was covered in the lesson on recursion on lists. This lesson reverses only part of the list at a time. The list is cut into blocks of k nodes. Each full block is reversed in place, which means the nodes are rearranged inside the same list without making a new list. A last block with fewer than k nodes is left as it is. The blocks are then joined back together in their original order.

The problem looks like one job, but it has three jobs inside it. The code must find the end of a block, reverse the nodes of that block, and attach the block to the blocks before and after it. Most bugs in this problem come from one of those three jobs. Each job is shown on its own in the worked examples before the code is put together.

The reversal itself uses the same three-variable loop from the recursion lesson. The new part is the joining. Swapping only two nodes at a time, as in the earlier lesson on swapping nodes in pairs, is the case where k is 2.

Plain words for the parts

A node holds one value and a next link to the node after it. In Python, a node is an object, and its link is an attribute that holds another node object. The last node has next set to None, which is Python's word for "nothing here".

A block is a run of nodes next to each other in the list. A group in this lesson means the same thing as a block.

Reversing a block means the nodes keep their values, but their next links are turned around. The first node of the block becomes the last, and the last becomes the first. The node after the block must be remembered first, so that the list is not cut off.

Reconnecting means changing the link from the node before a block to point at the new first node of the block. Without this step, the block is reversed but nothing points at it.

Dummy node is an extra node placed before the real first node. It holds no real value. The code can then treat the first block the same way as every other block, because every block has a node before it. The same idea is used for the sentinel in the lesson on doubly linked lists, but here the dummy is only a helper for the start of the list.

The code uses this node class. It has the same shape as the class in the recursion lesson. A class is a blueprint for making objects. The __init__ method runs when a new node is made, and self is the name for the node being set up.

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

The next_node=None part is a default. If you leave it out when you make a node, its next link is None.

Two helpers build a list from numbers and turn a list into text, so that results are easy to read.

def from_list(*values):
    head = None
    for value in reversed(values):
        head = Node(value, head)
    return head
 
 
def show(head):
    parts = []
    cur = head
    while cur is not None:
        parts.append(str(cur.value))
        cur = cur.next
    return " -> ".join(parts) if parts else "(empty)"

The *values in from_list means "any number of arguments". Python collects them into a tuple, which is a fixed sequence that cannot be changed. The call from_list(1, 2, 3) gives values the value (1, 2, 3). The reversed function walks the tuple from the end, so each new node is placed in front of the nodes already built.

In show, parts is a list of text pieces. The " -> ".join(parts) call glues the pieces together with the arrow between them.

Testing for a missing node uses is None and is not None. The word is checks whether two names point at the same object. Every missing node is the one object called None, so is is the right test.

Worked example 1: find the end of a block

Before reversing anything, the code must know where a block ends. It starts at the node before the block and moves forward k steps. The node it stops on is the last node of the block. This node is called kth in the code, because it is the k-th node counted from the start of the block.

Take the list 1 -> 2 -> 3 -> 4 -> 5 with k set to 2. The node before the first block is the dummy node. Here is the search.

kth = group_prev
for _ in range(k):
    if kth is None:
        break
    kth = kth.next

The range(k) call gives k steps. The loop variable is named _ because the code does not use its value. The break stops the loop early when the list ends.

The loop moves two steps. The first step goes from the dummy to 1. The second goes from 1 to 2. So kth is node 2, the last node of the first block.

The search also detects a short block. If the list ends before k steps are taken, kth becomes None. Take the same list with k set to 3. The search takes step one to 1, step two to 2, and step three to 3, so kth is node 3. Now set k to 6. The list has only five nodes, so the sixth step goes past the end and kth becomes None, which tells the code that the block is short.

Here is a check that prints the block found for each case. The f"..." text is an f-string. A part written as {kth.value} inside an f-string is replaced by the value of kth.value.

def find_block(head, k):
    group_prev = Node(0, head)
    kth = group_prev
    for _ in range(k):
        if kth is None:
            break
        kth = kth.next
    if kth is None:
        print("short block, nothing to reverse")
    else:
        print(f"block ends at {kth.value}")

Calling find_block(from_list(1, 2, 3, 4, 5), 2) prints block ends at 2, and with k set to 3 it prints block ends at 3. Calling it with k set to 6 prints short block, nothing to reverse. A run printed these three lines in this order.

block ends at 2
block ends at 3
short block, nothing to reverse

Worked example 2: reverse one block and keep the rest

Next, reverse one block. The reversal needs the node after the block, which is called group_next. It is saved before any link changes. Here is the rule for the reversal. The variable prev starts at group_next, not at None. So the old first node of the block ends up pointing at the node after the block, and no link is lost.

Take the list 1 -> 2 -> 3 -> 4 -> 5 again. The block is 1 and 2, so group_next is node 3. The reversal loop runs while cur is not group_next. The check uses is not because the loop is comparing nodes, and it must stop on that exact node.

group_next = kth.next
prev = group_next
cur = group_prev.next
while cur is not group_next:
    nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt

The name nxt is used for the saved next node. The name next is avoided here, because next is also a built-in function in Python.

Here is what happens step by step. The starting point is the dummy, which links to 1, which links to 2, which links to 3.

start:  prev = 3   cur = 1
step 1: nxt = 2; 1.next = 3; prev = 1; cur = 2
        now 1 points at 3
step 2: nxt = 3; 2.next = 1; prev = 2; cur = 3
        cur is group_next, so the loop stops
result: 2 -> 1 -> 3 -> 4 -> 5

The block is now 2 -> 1, and node 1 points at 3, which is the node after the block. The rest of the list was not touched. Notice that prev ends as node 2, which is the new first node of the block. The loop does not return that value, so the code must remember the new first node itself.

Worked example 3: reconnect the blocks and move on

The last step joins the reversed block to the list before it, and then moves on to the next block. The variable group_prev marks the node before the current block. After the reversal, the node before the block must point at kth, the new first node. The old first node of the block, which is now the last node of the block, becomes the new group_prev.

Here is the rest of the first pass for the list 1 -> 2 -> 3 -> 4 -> 5 with k set to 2. The variable old_first is saved before the link changes, because after the change it is hard to find the old first node.

old_first = group_prev.next
group_prev.next = kth
group_prev = old_first

The first pass starts with group_prev at the dummy and old_first at node 1. After the reconnect, the dummy points at node 2, and group_prev is node 1. The next pass finds the second block from node 1. Its kth is node 4, and its group_next is node 5. The reversal of 3 and 4 gives 4 -> 3 -> 5. The reconnect sets node 1 to point at 4. Then group_prev is node 3, and the search from node 3 finds that only node 5 is left. That block is short, so the loop stops.

The joined result is 2 -> 1 -> 4 -> 3 -> 5. Here is the whole program, with the three jobs placed in one loop. The function returns dummy.next, not head, as explained after the code.

The if __name__ == "__main__": line runs the prints only when this file is started directly. If another file imports reverse_in_groups, the prints are skipped.

The function returns dummy.next, not head. The first real node may have moved, because the first block was reversed. The dummy node always points at the true first node, so the answer is read from it.

The output of the program above, from one run, is this.

k=2 on 1..5: 2 -> 1 -> 4 -> 3 -> 5
k=3 on 1..8: 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8
k=1 on 1..3: 1 -> 2 -> 3
k=4 on 1..10: 4 -> 3 -> 2 -> 1 -> 8 -> 7 -> 6 -> 5 -> 9 -> 10
k=2 on empty: (empty)
k=5 on 1..3: 1 -> 2 -> 3

The k set to 1 leaves the list unchanged, because each block is one node and reversing one node does nothing. The k set to 5 on a three-node list leaves the list unchanged, because the only block is short. The empty list returns as empty, because the first search finds kth to be None at once.

The guard if k < 1 stops the function before any work starts. It raises a ValueError, which is Python's built-in error for a value that is the right type but not allowed. The Common mistakes section below shows why the guard is needed.

Worked example 4: the same job with recursion

The loop above can also be written as recursion. A recursive function is one that calls itself. Each call handles one block, and the call for the rest of the list handles the other blocks. The recursion uses the same idea as the earlier lesson on recursion: solve the rest, then join the answer to your part.

def reverse_in_groups_recursive(head, k):
    kth = head
    for _ in range(k - 1):
        if kth is None:
            break
        kth = kth.next
    if kth is None:
        return head
    group_next = kth.next
    prev = group_next
    cur = head
    while cur is not group_next:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    rest_result = reverse_in_groups_recursive(group_next, k)
    head.next = rest_result
    return kth

The first lines find the end of the block. The count starts at k - 1, because kth already starts on head, which is one node into the block. If the block is short, the function returns the list unchanged. Otherwise it reverses the block, then asks for the rest of the list to be handled by a recursive call. The old head is now the last node of the block, so its next is set to the first node of the handled rest. The function returns kth, the new first node of this block.

Take the list 1 -> 2 -> 3 -> 4 -> 5 with k set to 2. The first call reverses 1 and 2, then calls itself on 3 -> 4 -> 5. That call reverses 3 and 4, then calls itself on 5. The call on 5 finds that the block is short and returns 5. The call on 3 sets node 3 to point at 5 and returns 4. The first call sets node 1 to point at 4 and returns 2. The output is 2 -> 1 -> 4 -> 3 -> 5, the same as the loop.

The recursive version makes one call for each block, so its depth is about the number of nodes divided by k. Python keeps a limit on how deep the calls can go. The default limit is 1000, which sys.getrecursionlimit() reports. When the limit is passed, Python raises a RecursionError. Raising the limit with sys.setrecursionlimit does not remove the cost, because each call still takes memory. For a long list with a small k, the loop is the safer choice.

Common mistakes

Each mistake below was run on purpose. The real output is shown.

Mistake 1: reversing a short last block. The loop must stop when the block is short. If the check is removed, the leftover nodes are reversed too. This version has no such check, so it reverses whatever nodes are left, with None as the end of the last block.

def reverse_all_groups(head, k):
    dummy = Node(0, head)
    group_prev = dummy
    while group_prev.next is not None:
        kth = group_prev
        for _ in range(k):
            if kth is None:
                break
            kth = kth.next
        group_next = None if kth is None else kth.next
        prev = group_next
        cur = group_prev.next
        first = cur
        while cur is not group_next:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        group_prev.next = prev
        group_prev = first
    return dummy.next

Run on the list 1 -> 2 -> 3 -> 4 -> 5 with k set to 3, the output was this.

reverse all groups k=3 on 1..5: 3 -> 2 -> 1 -> 5 -> 4

The task wants 3 -> 2 -> 1 -> 4 -> 5, because the short block 4, 5 should stay as it is. The output shows that block reversed. Keep the check, and stop the loop when the block is short.

Mistake 2: starting the reversal with None. The reversal must start prev at group_next, the node after the block. If prev starts at None, the last node of each block points at nothing, and the rest of the list is lost. Only the line that sets prev is changed here.

prev = None

With this change, the list 1 -> 2 -> 3 -> 4 -> 5 and k set to 2 produced this output.

bug prev null k=2 on 1..5: 2 -> 1

Nodes 3, 4 and 5 are gone from the result, because node 1 points at None. The program does not raise an error. The list is simply shorter than it should be, and that is harder to notice.

Mistake 3: moving the group marker to the wrong node. After the reconnect, the next block must start from the old first node of the block. If the code sets group_prev to kth, the marker lands on the new first node. The next reversal then starts from the wrong place. Only the last two lines are changed.

group_prev.next = kth
group_prev = kth

The same list with k set to 2 produced this output.

bug reconnect k=2 on 1..5: 2 -> 3 -> 4 -> 5 -> 1

The second block was joined to the wrong node, so the nodes are out of order and node 1 is at the end. The fix is to save the old first node in old_first before the reconnect, and move group_prev to it.

Mistake 4: returning the old head. The first block is usually reversed, so the first node of the list changes. The function must return dummy.next. Returning head gives the node that is now the last node of the first block.

return head

With this change, the list 1 -> 2 -> 3 -> 4 -> 5 and k set to 2 produced this output.

bug return head k=2 on 1..5: 1 -> 4 -> 3 -> 5

The answer starts at the wrong node, and node 2 is no longer reachable from it. The result is missing a value. The fix is to return dummy.next.

Mistake 5: a k of zero or less. The search for the end of a block moves k steps. With k set to 0, the search moves no steps, so kth is the dummy node itself. The reconnect line then makes the dummy point at itself. Without the guard, one pass with k set to 0 makes dummy.next point at the dummy, which means the list loops, and the while True loop never ends. The guard at the start of the function stops this with a clear message.

if k < 1:
    raise ValueError("k must be at least 1")

Calling the function with k set to 0 gave this output from the program.

k=0 error: k must be at least 1

The output above comes from a call inside try and except, so the program printed one line and kept going. Without that, Python prints a traceback and stops.

Practice

The answer for each exercise is below its question. Each answer was run with the same node class and helpers as this lesson.

Exercise 1. What does the function return for the list 1 -> 2 -> 3 -> 4 -> 5 -> 6 with k set to 4? Work it out by hand, then check.

Show the answer

The first block is 1, 2, 3, 4, which reverses to 4 -> 3 -> 2 -> 1. The last block is 5, 6, which has fewer than four nodes, so it is left alone. The result is 4 -> 3 -> 2 -> 1 -> 5 -> 6. A run printed exercise 1, k=4 on 1..6: 4 -> 3 -> 2 -> 1 -> 5 -> 6.

Exercise 2. Write a function count_full_groups(head, k) that returns how many complete blocks of k nodes a list has. A short last block is not counted. For the list 1 -> 2 -> 3 -> 4 -> 5 with k set to 2 the answer is 2, and for the list 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 with k set to 3 the answer is 2.

Show the answer

def count_full_groups(head, k):
    n = 0
    cur = head
    while cur is not None:
        n += 1
        cur = cur.next
    return n // k

The function counts every node first, then divides by k with //. That is floor division, which drops the remainder, which is the short last block. A run printed full groups 1..5, k=2: 2 and full groups 1..7, k=3: 2.

Exercise 3. Change the function so that a short last block is also reversed. For the list 1 -> 2 -> 3 -> 4 -> 5 with k set to 3 the answer is 3 -> 2 -> 1 -> 5 -> 4.

Show the answer

Use the version with no short-block check from Mistake 1. The loop runs while group_prev.next is not None. When fewer than k nodes are left, kth becomes None, so group_next is set to None, and the reversal runs to the end of the list. The line group_prev.next = prev joins the block to the list before it. The run printed reverse all groups k=3 on 1..5: 3 -> 2 -> 1 -> 5 -> 4.

Exercise 4. Predict the output for the list 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 with k set to 3. Then check it.

Show the answer

The blocks are 1, 2, 3, which become 3 2 1, and 4, 5, 6, which become 6 5 4. The last node, 7, is a short block and stays as it is. The output is 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7. A run printed exercise 4, k=3 on 1..7: 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7.

Exercise 5. The recursive version makes one call per block. Explain in your own words why a list of 100,000 nodes with k set to 2 is a bigger risk for the recursive version than for the loop, and which version you would ship.

Show the answer

With k set to 2, the recursive version makes about 50,000 nested calls, one for each pair of nodes. Each call takes a frame on the call stack, which is the memory Python uses to keep track of the calls that are still waiting to finish. The recursion lesson explained this. Python stops at the default limit of 1000, so the call fails. A run with 100,000 nodes printed recursive error type: RecursionError message: maximum recursion depth exceeded. The loop makes no nested calls and uses the same few variables from start to finish. A run of the loop on the same 100,000 nodes finished, and the first six values were 2, 1, 4, 3, 6, 5 as expected. The loop is the version to ship, because its memory use does not depend on the length of the list. The recursive version is shorter to read and is fine for short lists.

Summary

• A block is found by moving k steps from the node before it. If the search reaches None first, the block is short and is left alone.
• A block is reversed with prev starting at the node after the block, so no link is lost.
• After a reversal, the node before the block points at the new first node, and the old first node becomes the marker for the next block.
• The answer is read from the dummy node, because the first block may have moved.
• The recursive version is short, but its depth grows with the number of blocks, and Python caps that depth, so the loop is safer for long lists.