Reverse Nodes in K Group

First check whether at least k nodes remain from the current position — if not, this is a trailing partial group, so return it unreversed. Otherwise, reverse exactly k nodes using the standard iterative reversal, then recursively solve the rest of the list and attach it after the original head (which is now the tail of this reversed group).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseKGroup(self, head: ListNode | None, k: int) -> ListNode | None:
        node = head
        count = 0
        while node and count < k:
            node = node.next
            count += 1
        if count < k:
            return head   # fewer than k nodes left: leave them as-is

        prev, curr = None, head
        for _ in range(k):
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        head.next = self.reverseKGroup(curr, k)   # head is now the tail of this group
        return prev

Clean and mirrors the group structure directly, but the recursion creates one stack frame per group, so the call stack grows to O(n/k) frames — the iterative version below avoids that to satisfy the O(1) follow-up.

Use a dummy node before head and a group_prev pointer that always sits just before the group currently being reversed. For each group: first scan ahead k nodes to confirm a full group exists (returning early if not), then reverse that group in place using the same three-pointer technique, and finally reconnect group_prev to the new head of the reversed group before advancing group_prev to what is now the group’s tail.

class Solution:
    def reverseKGroup(self, head: ListNode | None, k: int) -> ListNode | None:
        dummy = ListNode(0, head)
        group_prev = dummy

        while True:
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next   # fewer than k nodes left: done

            group_next = kth.next        # first node after this group
            prev, curr = group_next, group_prev.next
            while curr != group_next:
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node

            tmp = group_prev.next        # this group's original head, now its tail
            group_prev.next = kth        # kth is now this group's head
            group_prev = tmp

Tracing head = [1,2,3,4,5], k = 2:

Why it’s correct: each full group is reversed with the same proven-correct in-place reversal, and group_prev always points to the node immediately before the next group to process — so reconnecting group_prev.next to the reversed group’s new head preserves the chain between groups. The upfront k-node lookahead guarantees a trailing partial group is detected and left untouched, exactly matching the problem’s requirement. Complexity: each node is visited a constant number of times — once during the lookahead scan and once during reversal — across all groups → O(n) time. Only a fixed number of pointer variables are used, with no recursion or auxiliary data structure → O(1) extra space — this satisfies the follow-up and is optimal, since every node’s next pointer must be touched at least once to reverse it.