Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The list must be processed in consecutive chunks of size k.

If a full chunk exists, those k nodes should be reversed in place. If fewer than k nodes remain at the end, that tail must stay exactly as it is.

Two details matter:

  • the algorithm is not allowed to swap node values
  • the final partial group must remain untouched

So the real task is:

repeatedly isolate the next complete group of k nodes, reverse only that group, and reconnect it cleanly to the already-processed prefix and the untouched suffix.

Why the obvious ideas are not the final answer

One straightforward approach is to copy nodes into an array, reverse each length-k slice, and rebuild the links. That is easy to reason about, but it uses O(n) extra space and misses the linked-list follow-up.

Another common first attempt is to start reversing pointers as soon as nodes are seen. That becomes dangerous near the end of the list, because if the remaining suffix has fewer than k nodes, the algorithm must leave those nodes unchanged. Reversing first and checking later creates extra work and pointer-repair edge cases.

The clean solution is to look ahead before touching the current group.

The key insight

Each group can be handled independently once three boundaries are known:

  • group_previous: the node just before the group
  • group_end: the kth node in the group
  • group_successor: the node right after the group

If group_end does not exist, the work is done and the remaining suffix stays unchanged.

If it does exist, then the nodes from group_previous.next through group_end form a closed segment that can be reversed with the standard linked-list reversal pattern. The useful trick is to initialize previous to group_successor. That way, when the reversal finishes, the old group head automatically becomes the new tail and already points at the correct next segment.

How to derive the optimal in-place solution

A practical interview derivation looks like this:

  1. Notice that the list is transformed block by block, so each decision is local to the next k nodes.
  2. Realize that the final partial block is special, so the code must verify that a full block exists before modifying pointers.
  3. Reuse the standard in-place linked-list reversal pattern on exactly one closed-open segment: [group_start, group_successor).
  4. Add a sentinel node before the head so reconnecting the first reversed group is no harder than reconnecting any later group.

That gives a loop with one repeated pattern:

  1. Find the next full group.
  2. Reverse it.
  3. Stitch it back into the list.
  4. Advance to the next group.

Why this is the best general answer

The in-place iterative solution is usually the strongest interview answer:

  • Time: O(n)
  • Extra space: O(1)

Each node is visited only a constant number of times across the group lookahead and the reversal work, so the total running time stays linear.

There is also a recursive solution that is elegant and correct, but it uses call-stack space. Because the official follow-up asks for O(1) extra memory, the iterative pointer solution is the better final answer.

Python solution

The implementation below keeps the logic split into two helpers:

  • one helper checks whether a full group exists
  • one helper reverses exactly one group and returns its new head and new tail

That keeps the main loop short and makes the reconnection logic easy to verify.

from typing import Optional, Tuple


# LeetCode provides the ListNode class.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def reverseKGroup(
        self,
        head: Optional["ListNode"],
        k: int,
    ) -> Optional["ListNode"]:
        if k <= 0:
            raise ValueError("k must be a positive integer")

        if head is None or k == 1:
            return head

        sentinel = ListNode(0, head)
        group_previous = sentinel

        while True:
            group_end = self._find_group_end(
                group_previous=group_previous,
                group_size=k,
            )
            if group_end is None:
                break

            group_start = group_previous.next
            group_successor = group_end.next

            reversed_group_head, reversed_group_tail = self._reverse_group(
                group_start=group_start,
                group_successor=group_successor,
            )

            group_previous.next = reversed_group_head
            reversed_group_tail.next = group_successor
            group_previous = reversed_group_tail

        return sentinel.next

    @staticmethod
    def _find_group_end(
        group_previous: "ListNode",
        group_size: int,
    ) -> Optional["ListNode"]:
        current = group_previous

        for _ in range(group_size):
            current = current.next
            if current is None:
                return None

        return current

    @staticmethod
    def _reverse_group(
        group_start: "ListNode",
        group_successor: Optional["ListNode"],
    ) -> Tuple["ListNode", "ListNode"]:
        previous = group_successor
        current = group_start

        # Reverse the closed-open segment [group_start, group_successor).
        while current is not group_successor:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node

        # `previous` is the new head, and the old head becomes the new tail.
        return previous, group_start

Why this works

Before each loop iteration, group_previous.next is the first node of the yet-to-be-processed suffix.

If there are not k nodes ahead, the algorithm stops immediately, so the remaining suffix is preserved unchanged exactly as the problem requires.

If there are k nodes ahead, the algorithm reverses only that segment and reconnects it in two pointer writes:

  • group_previous.next points to the new head of the reversed group
  • the new tail points to group_successor

Then group_previous moves to the tail of the reversed group, so the same invariant is ready for the next iteration.

Because the loop never loses track of the node before the group and the node after the group, the list remains fully connected throughout the transformation.

Interview follow-ups

Could you solve this recursively instead of iteratively?

Yes. A recursive solution first checks whether the next k nodes exist. If they do, it recursively solves the rest of the list starting after that group, then reverses the current group and connects its tail to the recursively processed remainder. This works because each call handles one block and delegates the suffix to the next call. The time complexity remains O(n), but the extra space becomes proportional to the recursion depth, which is O(n / k) groups and O(n) in the worst case when k is small. That is why recursion is elegant but not the best answer for the O(1)-space follow-up.

What changes if the final partial group should also be reversed?

Then the lookahead rule changes. In the standard problem, failure to find k nodes means “stop and leave the rest alone.” In this variant, failure to find k nodes would instead mean “reverse whatever nodes are left.” The reversal helper itself does not need to change much, because it already knows how to reverse a bounded segment in place. What changes is the stopping condition and the problem semantics around the suffix. The complexity is still O(n) time and O(1) extra space, but the code must be careful not to preserve the leftover tail by default.

Why is the sentinel node worth using here?

Without a sentinel, the first group is awkward because reversing it changes the real head of the list. That forces a special case for reconnecting the new head. The sentinel removes that special case by giving every group, including the first one, a predecessor node. This works because pointer rewiring is then uniform across the entire list: find the predecessor, reverse the group, reconnect, move on. The asymptotic complexity does not change, but the implementation becomes much easier to reason about and much less error-prone.

How would you explain the O(n) time bound if each group is both scanned and reversed?

The easiest explanation is amortized across the whole list. Every iteration does a k-step lookahead and a k-node reversal for one complete group, so each complete group costs O(k) + O(k), which is still O(k). If there are about n / k such groups, the total work is O((n / k) * k) = O(n). In other words, the algorithm does not restart from the head for each group and does not nest a full traversal inside another full traversal. It only moves forward through the list with constant extra pointer bookkeeping.