Reverse Nodes in k-Group — Editorial

Opening the reading…

Intuitionreverse complete segments without ever losing the list

The list must be changed by links, so each complete group of k nodes has to be turned around while its nodes stay in memory. For one group, remember the node before it and the node after it. Reverse the arrows inside the group, then connect the old first node, which is now the group's tail, to the following node.

The final short group is special: it is not a group to reverse at all. Before changing any links, count ahead by k nodes. If fewer than k nodes remain, stop immediately. A dummy node before the original head gives every group a real predecessor, so reconnecting the first reversed group uses exactly the same pointer assignments as every later group.

Approachcount first, reverse second, reconnect last

Create a dummy node before head and set prev to it, because the first group has no natural predecessor and otherwise needs a separate head-update case.

Scan from prev->next for at most k nodes and leave cur at the first node after the group, because cur is the boundary that both protects the suffix and proves whether the group is complete.

If the scan counted fewer than k nodes, stop without touching any pointer, because the problem requires the incomplete final group to keep its original order.

Set start to prev->next, then reverse the links from start up to but not including cur. Keeping cur as the stopping boundary prevents the reversal from entering the next group.

After reversal, start is the group's tail, so set start->next to cur and prev->next to the new group head. Both assignments are necessary: one attaches the tail forward, and the other attaches the predecessor backward.

Move prev to start, because the old group head is now the finished group's tail and is exactly the predecessor needed by the next group.

Return dummy->next after all complete groups are processed, because the dummy itself is only a permanent anchor and is not part of the answer.

Complexityeach node crosses the reversal logic once

MEASURE	BOUND	WHY
Time	O(n)	The look-ahead scan and the reversal together process each node a constant number of times. Every successful iteration advances past a disjoint group, and the final unsuccessful scan stops after at most k nodes, so no node can be charged to unboundedly many groups.
Space	O(1) extra	Only a fixed number of ListNode pointers and the dummy node are used; the returned list is required output and is excluded from extra space. The bound stays O(1) for every input shape, including a list of n nodes and a final incomplete group.

Here n is the number of nodes and k is the requested group size; the bound does not depend on the values stored in the nodes.

Annotated solutionC++ · iterative in-place pointer reversal

CPPIterative solution that counts a complete group, reverses its links, and reconnects both ends.

#include <vector>

using namespace std;

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;

        while (prev->next != nullptr) {
            ListNode* cur = prev->next;
            int count = 0;

            while (cur != nullptr && count < k) {
                cur = cur->next;
                ++count;
            }

            if (count < k) {
                break;
            }

            ListNode* start = prev->next;
            ListNode* groupEnd = cur;
            ListNode* before = start;
            ListNode* node = start->next;

            while (node != groupEnd) {
                ListNode* next = node->next;
                node->next = before;
                before = node;
                node = next;
            }

            start->next = groupEnd;
            prev->next = before;
            prev = start;
        }

        return dummy.next;
    }
};

The reversal starts with before = start rather than nullptr because start is the first node in the group and must eventually point toward the preceding part of the list. The loop stops when node reaches groupEnd, so the first node after the group is never modified. Afterward, start has become the tail, while before holds the new head.

The recursive alternativethe same grouping idea, with call-stack space instead of constant extra space

A recursive solution can first walk k nodes to verify that a complete group exists. It then reverses those k links, recursively processes the suffix beginning at the old head's next pointer, and connects that processed suffix to the old head. This is a different arrangement of the same in-place operation, not a time optimisation: it is shorter conceptually but uses one call frame per group.

CPPRecursive grouping alternative; each call handles one complete group and leaves a short suffix untouched.

#include <vector>

using namespace std;

class Solution {
    ListNode* reverseFirstK(ListNode* head, int k) {
        ListNode* previous = nullptr;
        ListNode* current = head;

        while (k > 0) {
            ListNode* next = current->next;
            current->next = previous;
            previous = current;
            current = next;
            --k;
        }

        head->next = current;
        return previous;
    }

public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* node = head;
        int count = 0;

        while (node != nullptr && count < k) {
            node = node->next;
            ++count;
        }

        if (count < k) {
            return head;
        }

        ListNode* newHead = reverseFirstK(head, k);
        head->next = reverseKGroup(node, k);
        return newHead;
    }
};

The recursive version still runs in O(n) time and uses O(n / k) call-stack space, which is O(n) in the worst case when k is 1. It buys a direct statement of the repeated group operation, but the iterative version is the safer default for a hard linked-list problem because it keeps the extra space at O(1) and cannot overflow the runtime stack.