Reverse Nodes in k-Group

Reversing a linked-list segment is easy. Preserving everything on both sides of that segment is the real interview problem.

Read the Contract Before Touching a Pointer

You receive the head of a singly linked list and a positive integer k. Every complete block of k nodes must be reversed in place.

Three constraints define the solution:

• Change next pointers, not node values.
• Reverse complete groups independently, preserving the order of the groups.
• Leave a final group of fewer than k nodes unchanged.

For example:

Input:  1 → 2 → 3 → 4 → 5, k = 2
Output: 2 → 1 → 4 → 3 → 5

The nodes themselves remain the same objects. Only their connections change. Copying values into an array, reversing the array, and overwriting node values may produce the same serialized output, but it violates the structural contract.

The harder question is what happens during the first mutation. Once you change a node's next pointer, the original forward path may disappear. If you have not saved the untouched suffix, it is gone from your local view.

That gives us the central rule:

Before changing a link, identify the group predecessor, the group terminus, and the successor after the group.

Everything else follows from that boundary ownership.

Recognize the Bounded-Reversal Pattern

This problem has four recognition cues:

1. The list is divided into repeated fixed-size segments.
2. Each complete segment undergoes a local reversal.
3. A short remainder must remain untouched.
4. The mutation must happen through node links with constant auxiliary space.

The standard linked-list reversal primitive is only one part of the problem. The full solution has three separate obligations:

1. Detect whether at least k nodes remain.
2. Reverse exactly those k nodes.
3. Reconnect the reversed segment to the processed prefix and untouched suffix.

Candidates often combine these obligations too early. That is where pointer bugs start. A clean implementation treats each group as a temporary ownership boundary:

processed prefix | current group of k nodes | untouched suffix

The current iteration may mutate only the middle region. It must preserve a route into the suffix before mutation begins.

A brute-force baseline makes the intended structure clearer. You could collect nodes or values, reverse complete chunks in an auxiliary array, then rebuild or overwrite the list. That costs O(n) additional space and weakens the node-identity guarantee. The in-place solution exploits a simpler fact: a linked list already stores the sequence as pointers, so the reversal can happen directly in those pointers.

Fast and slow pointers are not the primary pattern here. They are useful when the decisive structure involves a midpoint, a cycle, or unequal traversal rates. This problem has none of those. Its decisive structure is fixed-size ownership and boundary preservation.

Name the Pointer Obligations

Use a dummy node before the real head:

dummy → head

The dummy removes the special case where the first group changes the list's head. Every group now has a predecessor that can be rewired in the same way.

For the current group, define:

Variable	Meaning
group_prev	Node immediately before the current group
kth	Last node in the current group
group_head	First node in the current group
group_next	First node after the current group

Before reversal, the structure is:

group_prev → group_head → ... → kth → group_next

After reversal, it must become:

group_prev → kth → ... → group_head → group_next

The original group_head becomes the new tail. That detail does double duty:

• Its next pointer must be repaired to group_next.
• It becomes the next group_prev, because the next group begins after this new tail.

Detection must happen before mutation. Start at group_prev and walk exactly k links. If you cannot reach a kth node, fewer than k nodes remain. Stop immediately. The incomplete suffix is already in the required order.

The most important saved pointer is group_next. The old kth.next link will be overwritten during reversal, so the suffix must be recorded first.

Derive the Iterative Solution

The algorithm follows a fixed sequence.

1. Establish the common predecessor

dummy = ListNode(0, head)
group_prev = dummy

The dummy gives the first group the same shape as every later group.

2. Find the end of a complete group

Walk from group_prev exactly k steps. If the pointer becomes None before completing those steps, return dummy.next. No mutation has occurred in the incomplete suffix.

3. Save the boundaries

Once kth exists:

group_head = group_prev.next
group_next = kth.next

At this point, the current group is still connected to the suffix.

4. Reverse only the group

Initialize:

prev = group_next
curr = group_head

Then reverse until curr reaches group_next.

Starting prev at group_next is a useful implementation choice. It means the original group head—the eventual tail—will point to the suffix as part of the normal reversal loop. There is no separate “repair the tail” operation afterward.

5. Reconnect and advance

After reversal:

• kth is the new head of the group.
• group_head is the new tail.
• group_prev.next must point to kth.
• group_prev advances to group_head.

The loop then starts at the first node after the processed group.

Here is the state transition for 1 → 2 → 3 → 4 → 5 with k = 2:

Stage	Processed prefix	Current group	Suffix
Start	empty	1 → 2	3 → 4 → 5
After group 1	2 → 1	3 → 4	5
After group 2	2 → 1 → 4 → 3	incomplete 5	empty

The result is:

2 → 1 → 4 → 3 → 5

Notice what did not happen: node 5 was never reversed, detached, or temporarily redirected. Detection stopped before mutation.

A recursive formulation is also possible: reverse the first complete group, recursively process the remainder, and connect the old head to the recursive result. That can make the decomposition elegant, but it consumes call-stack space. For this problem, the iterative state machine is preferable in an interview because it exposes the exact boundaries and satisfies the constant-space requirement directly.

Prove Reachability and Progress

A pointer solution is not complete because its output looks correct on one example. We need to know that every original node remains reachable exactly once.

Use this loop invariant:

Before each iteration, dummy.next reaches all previously processed complete groups in final order. group_prev is the tail of that processed prefix, and group_prev.next begins the unprocessed suffix in its original order.

The proof has four parts.

Detection preserves an incomplete suffix

Suppose fewer than k nodes remain. The detection walk cannot reach a valid kth node, so the algorithm returns without changing any pointer in the suffix.

The already-processed prefix still ends at group_prev, whose next pointer reaches the suffix. Therefore the incomplete group remains connected and unchanged.

Bounded reversal preserves node identity

For a complete group, the reversal loop processes exactly the nodes from group_head through kth.

On each iteration:

1. Save curr.next in nxt.
2. Redirect curr.next to prev.
3. Move prev to curr.
4. Move curr to nxt.

Because nxt is saved before the mutation, the scan never loses the next node in the group. Because the loop stops when curr is group_next, it never modifies a node outside the group.

Every one of the k original nodes appears once in the reversed chain.

Reconnection restores the global chain

After the reversal loop:

prev = kth
group_head.next = group_next

The local chain is correct. Assigning:

group_prev.next = kth

connects the processed prefix to the reversed group.

The original group head now leads to group_next, so the reversed group also reaches the untouched suffix. No node is stranded.

Advancement guarantees termination

The original group_head is now the tail of the reversed group. Assigning:

group_prev = group_head

moves the boundary strictly forward by k nodes.

Since the list is finite, eventually either all nodes are processed or fewer than k nodes remain. The loop terminates.

By induction over complete groups, the final list contains every original node exactly once, reverses each complete block, preserves the order of the blocks, and leaves a short trailing block unchanged.

That is the k-group pointer invariant: the prefix is final, the current group is bounded, and the suffix has a saved entrance.

Dry-Run the Failure Boundaries

Most pointer implementations survive the ordinary example. They fail at boundaries. Test the boundaries deliberately.

k = 1

Every group contains one node, so the visible list does not change.

The algorithm still has work to do: it must advance group_prev after each group. If it leaves group_prev in place, the same node is detected repeatedly and the loop never progresses.

With k = 1, the reversal loop performs one link assignment per node, restoring the same connection.

Exact multiple of k

For:

1 → 2 → 3 → 4, k = 2

the output is:

2 → 1 → 4 → 3

The final reversed tail must point to None. This is handled by setting prev = group_next, where group_next is None for the last group.

A stale link here can create a cycle, such as 3 → 4 → 3, or accidentally preserve an old forward edge.

Short trailing group

For:

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

the first group becomes:

3 → 2 → 1

Then detection starts at node 1 and finds only 4 → 5. Because the second group is incomplete, the algorithm returns:

3 → 2 → 1 → 4 → 5

The important test is not merely the output values. Verify that no reversal code ran on 4 or 5.

k = n

The entire list is one complete group. Reverse once and ensure the new tail points to None.

Empty and single-node lists

The stated constraints describe a nonempty list with k <= n, but a defensive method can still handle:

• head is None
• a one-node list
• k == 1

These cases should return without error.

Common pointer failures

Failure	Observable consequence
Forgetting group_next	The untouched suffix becomes unreachable
Reversing before checking group size	The short suffix is reversed incorrectly
Advancing from kth	The next predecessor boundary is wrong
Advancing from the old group_prev	The same group can be processed again
Connecting the old head to the wrong node	Groups become disconnected or interleaved
Returning head	The first reversed group is skipped from the result
Failing to terminate the last group	A stale link can create a cycle

For serious validation, inspect structure rather than only serialized values. Track the original node identities and confirm that:

• Every original node is reachable exactly once.
• No cycle exists.
• The final node's next is None.
• The short suffix preserves its original order.
• Node values were never assigned.

Implement the Python Solution

Assume the usual ListNode shape, with val and next fields.

class Solution:
    def reverseKGroup(self, head: ListNode | None, k: int) -> ListNode | None:
        if head is None or k <= 1:
            return head

        dummy = ListNode(0, head)
        group_prev = dummy

        while True:
            # Find the kth node without changing any links.
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if kth is None:
                    # Fewer than k nodes remain; leave them unchanged.
                    return dummy.next

            group_head = group_prev.next
            group_next = kth.next

            # Reverse exactly [group_head, kth].
            # Starting prev at group_next repairs the new tail in-place.
            prev = group_next
            curr = group_head

            while curr is not group_next:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt

            # kth is the new head; group_head is the new tail.
            group_prev.next = kth
            group_prev = group_head

Each variable has one job:

• group_prev owns the connection from the processed prefix.
• kth proves that a complete group exists and identifies its end.
• group_head identifies the first node and later becomes the new tail.
• group_next protects the untouched suffix.
• prev, curr, and nxt perform the bounded reversal.

The order of assignments matters. In particular, this line must happen before any reversal:

group_next = kth.next

And this line must happen before advancing:

group_prev.next = kth

Otherwise the processed prefix has no route into the new group head.

If your interview environment does not support the union-type annotation, use the platform's expected signature or remove the annotations. The pointer logic is unchanged.

Complexity and Interview Validation

Let n be the number of nodes.

The algorithm takes O(n) time. Each complete group is scanned once to locate its kth node and then traversed once during reversal. Across all groups, those scans cover the list a constant number of times, so the total work is linear.

The iterative solution uses O(1) auxiliary space:

• A dummy node.
• A fixed number of local pointers.
• No array, set, copied node list, or recursion stack.

The input nodes themselves are not counted as auxiliary space. The dummy node is a constant-sized helper.

A compact validation matrix:

Case	Expected structural behavior
k = 1	Same order; boundary advances
Exact multiple	Every group reverses; final tail points to None
Short trailing group	Complete prefix reverses; suffix stays unchanged
k = n	One full-list reversal
One node	Same node returned
Empty defensive case	None returned

In an interview, explain the solution in this order:

1. State the contract: complete groups reverse, incomplete suffix does not.
2. Name the boundary pointers.
3. Explain why group_next must be saved before mutation.
4. Reverse only the bounded segment.
5. Reconnect the prefix and suffix.
6. State the reachability invariant.
7. Give time and space complexity.
8. Test k = 1, an exact multiple, and a short trailing group.

The transferable rule is simple:

Whenever a linked-list problem repeats a local mutation over bounded segments, identify the predecessor, terminal node, and successor before changing any link.

Save the successor. Mutate only the owned segment. Reconnect it. Advance from the node whose new role is guaranteed by the mutation. Then dry-run one complete group and one incomplete group, checking reachability after every assignment.