Reverse Nodes in k-Group

Description

Given the head of a singly linked list and a positive integer k, reverse the nodes of the list k at a time and return the modified list.

Specifically, take the first k nodes and reverse their order, then take the next k nodes and reverse their order, and so on. If the number of remaining nodes at the end is fewer than k, leave those nodes in their original order — do not reverse an incomplete group.

Important constraint: You may not change the values stored inside the nodes. Only the node connections (pointers / next references) may be rearranged.

Examples

Example 1

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

Output: [2, 1, 4, 3, 5]

Explanation: The list has 5 nodes. We process groups of 2:

Group 1: nodes [1, 2] → reversed to [2, 1]
Group 2: nodes [3, 4] → reversed to [4, 3]
Remaining: node [5] → only 1 node, which is less than k=2, so it stays as [5]

Final list: 2 → 1 → 4 → 3 → 5

Example 2

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

Output: [3, 2, 1, 4, 5]

Explanation: We process groups of 3:

Group 1: nodes [1, 2, 3] → reversed to [3, 2, 1]
Remaining: nodes [4, 5] → only 2 nodes, less than k=3, so they stay as [4, 5]

Final list: 3 → 2 → 1 → 4 → 5

Example 3

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

Output: [3, 2, 1, 6, 5, 4]

Explanation: The list has 6 nodes, which divides evenly into groups of 3:

Group 1: nodes [1, 2, 3] → reversed to [3, 2, 1]
Group 2: nodes [4, 5, 6] → reversed to [6, 5, 4]

Final list: 3 → 2 → 1 → 6 → 5 → 4

Constraints

The number of nodes in the list is n
1 ≤ k ≤ n ≤ 5000
0 ≤ Node.val ≤ 1000

Editorial

Brute Force

Intuition

The most straightforward way to think about this problem is to use extra memory to help us. Reversing a group of nodes in a linked list is tricky because pointers only go forward — you can't easily go backwards. But what if we collected the nodes into a temporary container?

Imagine you have a stack of plates. If you pick up plates one by one and stack them, then take them off the stack, they come out in reverse order. We can do the same thing here: use a stack to collect k nodes at a time, then pop them off (which reverses their order) and reconnect them.

For each group of k nodes:

Push k nodes onto the stack.
Pop them one by one, linking each popped node to the next.
Connect the reversed group to the previous part of the list.
If fewer than k nodes remain, don't reverse — just leave them.

This is easy to understand but uses O(k) extra space for the stack.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 3, 4, 5], k = 2:

Step 1: Create a dummy node pointing to head. This simplifies edge cases when the first group's new head becomes the list head. dummy → 1 → 2 → 3 → 4 → 5.

Step 2: Start at the first group. Count k=2 nodes: nodes 1 and 2 exist. We have a full group.

Step 3: Push node 1 onto the stack. Stack: [1].

Step 4: Push node 2 onto the stack. Stack: [1, 2]. We've collected k=2 nodes.

Step 5: Pop node 2 from stack. Link dummy → 2. Pop node 1 from stack. Link 2 → 1. Stack is empty. The group [1, 2] has been reversed to [2, 1].

Step 6: Remember that node 1 is the tail of this reversed group. It needs to connect to whatever comes next. Save node 1 as the previous group's tail.

Step 7: Move to the next group starting at node 3. Count k=2 nodes: nodes 3 and 4 exist. Full group.

Step 8: Push node 3, then node 4 onto the stack. Stack: [3, 4].

Step 9: Pop node 4. Link 1 → 4. Pop node 3. Link 4 → 3. Reversed group: [4, 3].

Step 10: Move to next group starting at node 5. Count k=2 nodes: only node 5 exists. That's less than k=2.

Step 11: Since remaining nodes (just node 5) are fewer than k, leave them as-is. Link 3 → 5.

Step 12: Return dummy.next = 2 → 1 → 4 → 3 → 5.

Brute Force — Using a Stack to Reverse K Nodes at a Time — Watch how we push k nodes onto a stack and pop them in reverse order, then reconnect the reversed group back into the list.

Algorithm

Create a dummy node pointing to head. Set prev_tail = dummy.
While there are nodes left to process:
a. Count k nodes ahead from the current position. If fewer than k nodes remain, stop (leave them as-is).
b. Push the next k nodes onto a stack.
c. Pop all nodes from the stack, linking each popped node after prev_tail.
d. The first node that was pushed (now the last popped) becomes the new tail. Update prev_tail to this node.
e. Connect the tail to the next unprocessed node.
Return dummy.next.

Code

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

        while (true) {
            // Count k nodes ahead
            ListNode* checker = prevTail;
            for (int i = 0; i < k; i++) {
                checker = checker->next;
                if (!checker) return dummy.next; // fewer than k left
            }

            // Push k nodes onto stack
            stack<ListNode*> stk;
            ListNode* curr = prevTail->next;
            for (int i = 0; i < k; i++) {
                stk.push(curr);
                curr = curr->next;
            }

            // Pop and relink
            ListNode* tail = prevTail->next; // will become tail after reversal
            while (!stk.empty()) {
                prevTail->next = stk.top();
                stk.pop();
                prevTail = prevTail->next;
            }
            prevTail->next = curr; // connect to remaining list
            prevTail = tail;       // tail of reversed group
            prevTail->next = curr;
        }
    }
};

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        prev_tail = dummy

        while True:
            # Count k nodes ahead
            checker = prev_tail
            for _ in range(k):
                checker = checker.next
                if not checker:
                    return dummy.next  # fewer than k left

            # Push k nodes onto stack
            stack = []
            curr = prev_tail.next
            for _ in range(k):
                stack.append(curr)
                curr = curr.next

            # Pop and relink
            tail = prev_tail.next  # will become tail after reversal
            while stack:
                prev_tail.next = stack.pop()
                prev_tail = prev_tail.next
            prev_tail.next = curr  # connect to remaining list
            prev_tail = tail       # tail of reversed group
            prev_tail.next = curr

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prevTail = dummy;

        while (true) {
            // Count k nodes ahead
            ListNode checker = prevTail;
            for (int i = 0; i < k; i++) {
                checker = checker.next;
                if (checker == null) return dummy.next;
            }

            // Push k nodes onto stack
            Deque<ListNode> stack = new ArrayDeque<>();
            ListNode curr = prevTail.next;
            for (int i = 0; i < k; i++) {
                stack.push(curr);
                curr = curr.next;
            }

            // Pop and relink
            ListNode tail = prevTail.next;
            while (!stack.isEmpty()) {
                prevTail.next = stack.pop();
                prevTail = prevTail.next;
            }
            prevTail.next = curr;
            prevTail = tail;
            prevTail.next = curr;
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the list once to count and once to push/pop, visiting each node a constant number of times. Total work is proportional to the number of nodes n.

Space Complexity: O(k)

The stack holds at most k nodes at any time. For each group of k nodes, we push k nodes and then pop them all before moving to the next group. Since k ≤ n, this is O(k) extra space.

Why This Approach Is Not Efficient

The stack-based approach works correctly in O(n) time, but it uses O(k) extra space for the stack. While k could be small (like 2), it could also be as large as n (where k = n means reversing the entire list), making the space usage O(n) in the worst case.

The follow-up challenge asks: can we solve this with O(1) extra memory? The stack is unnecessary overhead — we're only using it because reversing a section of a linked list feels hard. But linked list reversal is actually a well-known O(1)-space operation: we just need to manipulate the next pointers of the nodes themselves.

Key insight: Instead of storing nodes in a stack, we can reverse k nodes in-place by adjusting their next pointers directly — using only a few temporary pointer variables. We first try a recursive approach (which is more intuitive), then move to a fully iterative solution.

Better Approach - Recursion

Intuition

The recursive approach breaks the problem into smaller subproblems naturally:

Check if there are at least k nodes from the current position. If not, return the list as-is.
Reverse the first k nodes using the standard linked list reversal technique (three-pointer: prev, curr, next).
Recurse on the remaining list (starting from the (k+1)-th node) and connect the tail of the reversed group to whatever the recursion returns.

Think of it like a chain of dominos: you reverse the first k dominos, then hand the rest of the chain to your friend (the recursive call) who does the same thing. Each friend only worries about their k dominos and trusts the next friend to handle the rest.

The recursive structure is elegant, but the recursion stack adds O(n/k) space, since we make one recursive call for every group of k nodes.

Step-by-Step Explanation

Let's trace with head = [1, 2, 3, 4, 5], k = 2:

Step 1: Check if ≥ 2 nodes exist from node 1. Yes (nodes 1 and 2). Proceed to reverse.

Step 2: Reverse the first k=2 nodes using three pointers:

prev = null, curr = 1, next_node = 2
Set 1.next = null (prev), move prev = 1, curr = 2.

Step 3: Continue reversal:

next_node = 3 (saved), set 2.next = 1, move prev = 2, curr = 3.
We've reversed 2 nodes. prev = 2 (new head of this group), node 1 is the tail.

Step 4: Recurse on the remaining list starting from node 3. The recursive call will handle [3, 4, 5] with k=2.

Step 5: (Inside recursion) Check if ≥ 2 nodes exist from node 3. Yes (nodes 3 and 4). Reverse them:

Reverse [3, 4] → becomes [4, 3]. Node 3 is the tail.

Step 6: (Inside recursion) Recurse on remaining [5] with k=2. Only 1 node, fewer than k. Return node 5 as-is.

Step 7: (Back in inner recursion) Connect tail node 3 to the result of recursion: 3.next = 5.

Inner result: 4 → 3 → 5.

Step 8: (Back in outer call) Connect tail node 1 to the result of inner recursion: 1.next = 4.

Final result: 2 → 1 → 4 → 3 → 5.

Recursive Reversal — Reverse First K, Then Recurse on Rest — Watch how we reverse the first k nodes using pointer manipulation, then recursively handle the rest of the list, connecting groups as recursion unwinds.

Algorithm

Base case: Count k nodes from head. If fewer than k exist, return head unchanged.
Reverse first k nodes: Use the standard three-pointer reversal (prev, curr, next_node). After k iterations, prev points to the new head and the original head becomes the tail.
Recurse: Call the function recursively on the (k+1)-th node (the node after the reversed group).
Connect: Set the tail's next pointer to the result of the recursive call.
Return: Return the new head (prev) of the reversed group.

Code

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // Check if we have k nodes
        ListNode* checker = head;
        for (int i = 0; i < k; i++) {
            if (!checker) return head; // fewer than k nodes
            checker = checker->next;
        }

        // Reverse first k nodes
        ListNode* prev = nullptr;
        ListNode* curr = head;
        for (int i = 0; i < k; i++) {
            ListNode* nextNode = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextNode;
        }

        // head is now the tail of the reversed group
        // curr is the start of the next group
        head->next = reverseKGroup(curr, k);

        return prev; // new head of this group
    }
};

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        # Check if we have k nodes
        checker = head
        for _ in range(k):
            if not checker:
                return head  # fewer than k nodes
            checker = checker.next

        # Reverse first k nodes
        prev = None
        curr = head
        for _ in range(k):
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        # head is now the tail of the reversed group
        # curr is the start of the next group
        head.next = self.reverseKGroup(curr, k)

        return prev  # new head of this group

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // Check if we have k nodes
        ListNode checker = head;
        for (int i = 0; i < k; i++) {
            if (checker == null) return head;
            checker = checker.next;
        }

        // Reverse first k nodes
        ListNode prev = null;
        ListNode curr = head;
        for (int i = 0; i < k; i++) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }

        // head is now the tail of the reversed group
        head.next = reverseKGroup(curr, k);

        return prev; // new head of this group
    }
}

Complexity Analysis

Time Complexity: O(n)

Each node is visited exactly twice: once during the counting step and once during the reversal step. With n total nodes, the total work is O(2n) = O(n).

Space Complexity: O(n/k)

The recursion depth equals the number of groups, which is ⌈n/k⌉. Each recursive call uses O(1) space on the call stack (just local variables). In the worst case when k=1 (no reversal), the recursion depth is n, giving O(n) space. When k is large, the space is much smaller.

Why This Approach Is Not Efficient

The recursive approach achieves O(n) time and eliminates the need for a stack data structure, but it still uses O(n/k) space for the recursion call stack. When k is small (like 1 or 2), the recursion depth approaches n/2 or even n, which isn't ideal for very long lists.

The problem's follow-up explicitly asks for O(1) extra memory — meaning no recursion stack and no auxiliary data structures. We need a purely iterative solution that manipulates pointers in-place.

Key insight: We can convert the recursive logic to iterative by using a dummy node and a loop. Instead of recursion connecting groups, we manually track the tail of the previous group and link it to the new head of the next reversed group. This eliminates the call stack entirely.

Optimal Approach - Iterative In-Place Reversal

Intuition

The optimal approach reverses each group of k nodes directly in the list without any extra data structures or recursion. We iterate through the list, and for each group:

Check if k nodes are available (if not, we're done).
Reverse the k nodes in-place using the standard three-pointer technique.
Reconnect the reversed group: the previous group's tail points to the new head, and the current group's tail (which was the old head) points to the next unprocessed node.
Advance the pointer to process the next group.

The trick is managing the connections between groups. We use a dummy node before the head to simplify edge cases (the first group's new head becomes the overall list head). We also carefully track the tail of the previous group so we can connect it to the new head of the next reversed group.

Think of it like rearranging train carriages on a track: you detach a group of k carriages, reverse their order in-place, reattach them, then move down the track to the next group.

Step-by-Step Explanation

Let's trace with head = [1, 2, 3, 4, 5], k = 2:

Step 1: Create dummy node D. D → 1 → 2 → 3 → 4 → 5. Set group_prev = D (the node before the current group).

Step 2: Find the k-th node from group_prev. Starting from D: 1st node = 1, 2nd node = 2. The k-th node is 2. This confirms we have a full group.

Step 3: Save references: group_start = group_prev.next = 1, group_end = 2, next_group_start = group_end.next = 3.

Step 4: Reverse nodes between group_start and group_end. Using three pointers:

prev = 3 (next_group_start — the node after the group), curr = 1
Set 1.next = 3, prev = 1, curr = 2.
Set 2.next = 1, prev = 2, curr = 3 (done, curr passed group_end).
Now: 2 → 1 → 3 → 4 → 5.

Step 5: Reconnect: group_prev.next (D.next) = group_end (2). Now D → 2 → 1 → 3 → 4 → 5.

Step 6: Update group_prev = group_start (1). Node 1 is the tail of the reversed group.

Step 7: Find the k-th node from group_prev (node 1). 1st node = 3, 2nd node = 4. The k-th node is 4. Full group.

Step 8: group_start = 3, group_end = 4, next_group_start = 5. Reverse [3, 4]:

prev = 5, curr = 3. Set 3.next = 5, prev = 3, curr = 4.
Set 4.next = 3, prev = 4, curr = 5.
Now: 4 → 3 → 5.

Step 9: Reconnect: group_prev.next (1.next) = group_end (4). Now: D → 2 → 1 → 4 → 3 → 5.

Step 10: Update group_prev = group_start (3). Try to find k-th node from node 3: 1st = 5, 2nd = null. Can't find k=2 nodes. Stop.

Step 11: Return D.next = 2 → 1 → 4 → 3 → 5.

Optimal — Iterative In-Place K-Group Reversal — Watch how we reverse each group of k nodes by manipulating pointers directly, using only constant extra space. A dummy node simplifies the head-connection logic.

Algorithm

Create a dummy node D. Set D.next = head. Set group_prev = D.
Loop:
a. Starting from group_prev, count k nodes ahead to find the k-th node (group_end). If not found, break — no more full groups.
b. Record: group_start = group_prev.next, next_group_start = group_end.next.
c. Reverse the group in-place: Set prev = next_group_start, curr = group_start. For k iterations: save next, set curr.next = prev, advance prev and curr.
d. Reconnect: group_prev.next = group_end (the old end is now the new head of the reversed group).
e. Advance: group_prev = group_start (the old start is now the tail).
Return D.next.

Code

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

        while (true) {
            // Find the k-th node from groupPrev
            ListNode* kthNode = groupPrev;
            for (int i = 0; i < k; i++) {
                kthNode = kthNode->next;
                if (!kthNode) return dummy.next;
            }

            ListNode* groupStart = groupPrev->next;
            ListNode* nextGroupStart = kthNode->next;

            // Reverse k nodes in-place
            ListNode* prev = nextGroupStart;
            ListNode* curr = groupStart;
            for (int i = 0; i < k; i++) {
                ListNode* nextNode = curr->next;
                curr->next = prev;
                prev = curr;
                curr = nextNode;
            }

            // Reconnect
            groupPrev->next = kthNode;
            groupPrev = groupStart;
        }
    }
};

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

        while True:
            # Find the k-th node from group_prev
            kth_node = group_prev
            for _ in range(k):
                kth_node = kth_node.next
                if not kth_node:
                    return dummy.next

            group_start = group_prev.next
            next_group_start = kth_node.next

            # Reverse k nodes in-place
            prev = next_group_start
            curr = group_start
            for _ in range(k):
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node

            # Reconnect
            group_prev.next = kth_node
            group_prev = group_start

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode groupPrev = dummy;

        while (true) {
            // Find the k-th node from groupPrev
            ListNode kthNode = groupPrev;
            for (int i = 0; i < k; i++) {
                kthNode = kthNode.next;
                if (kthNode == null) return dummy.next;
            }

            ListNode groupStart = groupPrev.next;
            ListNode nextGroupStart = kthNode.next;

            // Reverse k nodes in-place
            ListNode prev = nextGroupStart;
            ListNode curr = groupStart;
            for (int i = 0; i < k; i++) {
                ListNode nextNode = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextNode;
            }

            // Reconnect
            groupPrev.next = kthNode;
            groupPrev = groupStart;
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

Each node is visited a constant number of times: once during the counting phase (finding the k-th node) and once during the reversal phase. Even though we count ahead for each group, the total counting work across all groups is O(n) because each node is counted at most once per group it belongs to. Total: O(n).

Space Complexity: O(1)

We use only a fixed number of pointer variables (dummy, groupPrev, kthNode, groupStart, nextGroupStart, prev, curr, nextNode). No recursion, no stack, no auxiliary arrays. The space is constant regardless of input size. This satisfies the follow-up challenge of O(1) extra memory.

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Reverse Nodes in k-Group

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Recursion

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Iterative In-Place Reversal

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis