Log inSign up
hardLeetCodeNot Started

Reverse Nodes in k-Group

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

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

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Explanation: Group 1 [1,2] -> [2,1], Group 2 [3,4] -> [4,3], Remaining node [5] is left unchanged.

Example 2:

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
Explanation: Group 1 [1,2,3] -> [3,2,1], Remaining nodes [4,5] (length 2 < 3) remain as they are.

Constraints:

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

1. Stack-Based k-Group Node Buffer

Intuition

1. Maintain an explicit stack st. 2. Traverse the list. Push nodes onto st. 3. When st.size() == k, pop nodes one by one and attach to the result list. 4. If traversal finishes and st contains < k nodes, retrieve the nodes in their original FIFO order (e.g. from the bottom of stack) and append them without reversal.

When to apply: Quick prototype leveraging LIFO stack properties.

Algorithm

  1. Traverse linked list with pointer curr.
  2. Push nodes into stack until k nodes are collected.
  3. Pop all nodes to reverse group and attach to tail.
  4. If leftover nodes < k, attach them without reversal.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3#include <vector>
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode() : val(0), next(nullptr) {}
9 ListNode(int x) : val(x), next(nullptr) {}
10 ListNode(int x, ListNode *next) : val(x), next(next) {}
11};
12
13class Solution {
14public:
15 ListNode* reverseKGroup(ListNode* head, int k) {
16 if (!head || k <= 1) return head;
17
18 ListNode dummy(0);
19 ListNode* tail = &dummy;
20 ListNode* curr = head;
21
22 while (curr != nullptr) {
23 std::vector<ListNode*> buffer;
24 ListNode* temp = curr;
25 while (temp != nullptr && buffer.size() < k) {
26 buffer.push_back(temp);
27 temp = temp->next;
28 }
29
30 if (buffer.size() == k) {
31 for (int i = k - 1; i >= 0; --i) {
32 tail->next = buffer[i];
33 tail = tail->next;
34 }
35 tail->next = nullptr;
36 curr = temp;
37 } else {
38 tail->next = curr;
39 break;
40 }
41 }
42
43 return dummy.next;
44 }
45};
46
47int main() {
48 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
49 Solution sol;
50 ListNode* res = sol.reverseKGroup(head, 2);
51 while (res != nullptr) {
52 std::cout << res->val << " ";
53 res = res->next;
54 }
55 std::cout << std::endl;
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(N) — Each node is pushed and popped from the stack once: O(N) overall.
  • Space complexity: O(k) — The stack stores at most k nodes at any time: O(k) extra memory.

2. Recursive k-Group Reversal

Intuition

1. Probe k steps from head with a pointer curr. 2. If count < k, return head without modifying. 3. Reverse the first k nodes using standard 3-pointer reversal. 4. Connect head.next = reverseKGroup(curr, k) (since original head is now the tail of this reversed group). 5. Return prev (new head of this reversed group).

When to apply: Clean, elegant recursive formulation.

Algorithm

  1. Count k nodes from head.
  2. If fewer than k nodes, return head as-is.
  3. Reverse first k nodes.
  4. Attach recursive call result to original head's next.
  5. Return new head (prev).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12public:
13 ListNode* reverseKGroup(ListNode* head, int k) {
14 ListNode* curr = head;
15 int count = 0;
16 while (curr != nullptr && count < k) {
17 curr = curr->next;
18 count++;
19 }
20
21 if (count == k) {
22 ListNode* reversedHead = reverseKGroup(curr, k);
23 while (count > 0) {
24 ListNode* nextTemp = head->next;
25 head->next = reversedHead;
26 reversedHead = head;
27 head = nextTemp;
28 count--;
29 }
30 head = reversedHead;
31 }
32 return head;
33 }
34};
35
36int main() {
37 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
38 Solution sol;
39 ListNode* res = sol.reverseKGroup(head, 2);
40 while (res != nullptr) {
41 std::cout << res->val << " ";
42 res = res->next;
43 }
44 std::cout << std::endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N) — Each node is visited once during probe and once during reversal: O(N) linear time.
  • Space complexity: O(N/k) recursion stack — The recursion stack depth is equal to the number of k-groups, which is O(N/k).

3. Iterative In-Place Pointer Reversal with Dummy Sentinel

Intuition

1. Initialize dummy sentinel dummy pointing to head, and groupPrev = dummy. 2. Helper getKth(curr, k) returns the kth node ahead or null if fewer than k nodes remain. 3. In a loop, find kth = getKth(groupPrev, k). If kth == null, break. 4. Save groupNext = kth.next. 5. Reverse the group: standard 3-pointer reversal starting from groupPrev.next up to groupNext. 6. Connect tmp = groupPrev.next; groupPrev.next = kth; groupPrev = tmp. 7. Return dummy.next.

When to apply: The definitive, optimal O(1) auxiliary space algorithm demanded in technical interviews.

Algorithm

  1. Initialize dummy with dummy.next = head, groupPrev = dummy.
  2. Find kth node from groupPrev.
  3. If null, break.
  4. Save groupNext = kth.next.
  5. Reverse nodes between groupPrev.next and groupNext.
  6. Rewire connections and advance groupPrev.
  7. Return dummy.next.

Linked List Interactive Dry Run

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Probe 2 nodes from groupPrev: kth node is node 2
Visual state
Values and pointers at this exact step
linked list
This linked list trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Why this step matters

Probe 2 nodes from groupPrev: kth node is node 2.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12private:
13 ListNode* getKth(ListNode* curr, int k) {
14 while (curr != nullptr && k > 0) {
15 curr = curr->next;
16 k--;
17 }
18 return curr;
19 }
20
21public:
22 ListNode* reverseKGroup(ListNode* head, int k) {
23 ListNode dummy(0, head);
24 ListNode* groupPrev = &dummy;
25
26 while (true) {
27 ListNode* kth = getKth(groupPrev, k);
28 if (kth == nullptr) break;
29
30 ListNode* groupNext = kth->next;
31 ListNode* prev = groupNext;
32 ListNode* curr = groupPrev->next;
33
34 while (curr != groupNext) {
35 ListNode* tmp = curr->next;
36 curr->next = prev;
37 prev = curr;
38 curr = tmp;
39 }
40
41 ListNode* tmp = groupPrev->next;
42 groupPrev->next = kth;
43 groupPrev = tmp;
44 }
45
46 return dummy.next;
47 }
48};
49
50int main() {
51 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
52 Solution sol;
53 ListNode* res = sol.reverseKGroup(head, 2);
54 while (res != nullptr) {
55 std::cout << res->val << " ";
56 res = res->next;
57 }
58 std::cout << std::endl;
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(N) — Each node is traversed once to locate the kth node and once during pointer reversal: 2N = O(N) time.
  • Space complexity: O(1) auxiliary — Uses only a few pointer variables (dummy, groupPrev, kth, curr, prev, nxt), requiring strictly O(1) auxiliary space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Stack-Based k-Group Node BufferO(N)O(k)Push nodes into a stack of capacity k. When k nodes are accumulated, pop them all to reverse the group and link into a new list. If end of list is reached with < k nodes, preserve their original order.High time complexity
2.Recursive k-Group ReversalO(N)O(N/k) recursion stackCheck if at least k nodes exist. If so, reverse the first k nodes, recursively process the rest of the list, and connect the tail to the returned head of the recursive result.—
3.Iterative In-Place Pointer Reversal with Dummy SentinelOptimalO(N)O(1) auxiliaryAnchor pointer groupPrev at the node before each group. Probe the kth node. Reverse the k nodes in-place using O(1) space, re-link group boundaries, and advance groupPrev to the tail of the reversed group.—

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Reversing the remaining tail group when its size is < k: the problem specification strictly requires leaving leftover nodes intact.

Pitfall 2:

Losing kth.next before reversing: must save groupNext = kth.next prior to pointer rewiring.

Pitfall 3:

Setting prev = null during sub-reversal instead of prev = groupNext: starting prev = groupNext directly links the reversed sublist's tail to the following group.

Back to DSA Sheet