Reverse Nodes in k-Group

Reverse Nodes in k-Group takes the classic "reverse a linked list" move and applies it in fixed-size chunks. It is a favorite because it forces you to be precise about pointers: you reverse a block, then stitch it back into the list without losing the rest.

The slow way first

You could copy the values into an array, reverse them in groups, then rebuild a brand-new list. That works and is easy to reason about, but it uses O(n) extra space and quietly ignores the point of the exercise — which is to manipulate the pointers in place.

The question to ask: can I reverse just one block at a time, in place, and reconnect it cleanly? If I can reverse a block of k nodes and know where its tail should point, I can repeat that for every block.

The idea: reverse one block, then recurse

Walk forward k steps first. If you cannot take k full steps, the remaining block is too short — leave it as-is and return its head untouched. Otherwise, reverse the next k nodes using a three-pointer walk (prev, cur, nxt), where prev is seeded with the already-reversed remainder of the list. The new head of the block becomes the head you return.

The key insight: by reversing the rest of the list first and passing its head in as prev, each block's tail automatically links to the next reversed block. No separate stitching step is needed.

Walk through it

Step through the animation. First we confirm two nodes (1, 2) remain — a full block. Then cur walks the block: node 1 flips to point past the block, prev and cur advance, and node 2 flips to point at 1. The block re-seats as 2 -> 1, and the same routine runs on 3 -> 4 -> 5, reversing 3, 4 and leaving 5 alone.

Pseudocode

count k nodes starting at head
if fewer than k nodes remain:
    return head                       # short block: leave it untouched
prev = reverse the rest of the list (start at the (k+1)-th node)
cur = head
repeat k times:                       # reverse this block, seeded with prev
    nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt
return prev                           # prev is the block's new head

The Python solution

def reverse_k_group(head, k):
    node = head
    count = 0
    while node and count < k:
        node = node.next
        count += 1
    if count < k:
        return head
    prev = reverse_k_group(node, k)
    cur = head
    for _ in range(k):
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

• The first while loop walks k steps to see whether a full block exists; node lands on the node just after the block.
• If count < k we hit a short trailing block, so we return head and leave it in original order.
• prev = reverse_k_group(node, k) reverses everything after this block first, so prev is the head we should link our reversed block onto.
• The for loop is the standard in-place reversal: save nxt, point cur.next back to prev, then slide both pointers forward.
• After k flips, prev is the new head of the reversed block, so we return prev.

Complexity

Every node is visited a constant number of times, so the time is O(n). The recursion adds one stack frame per block, giving O(n / k) space; an iterative version brings that down to O(1).

When this pattern shows up

Practice