Given the head of a singly linked list and an integer k, reverse the linked list nodes in groups of size k. Every group containing exactly k nodes must appear in reversed order. A final group containing fewer than k nodes must also appear in reversed order.
Return the head of the modified linked list. Node values can be changed only through pointer rearrangement logic, so linked list traversal and pointer manipulation form the main prerequisites.
Example 1
Input: head = [1, 2, 3, 4, 5, 6], k = 3
Output: [3, 2, 1, 6, 5, 4]
Explanation: Groups [1, 2, 3] and [4, 5, 6] contain three nodes each. Reversing both groups gives [3, 2, 1, 6, 5, 4].
Example 2
Input: head = [1, 2, 3, 4, 5], k = 2
Output: [2, 1, 4, 3, 5]
Explanation: Groups [1, 2] and [3, 4] are reversed. Final group [5] remains unchanged after reversal.
Brute Force Approach
In this approach, we process the linked list in groups of size at most k. For each group, we push the nodes into a stack. Since a stack follows Last In, First Out, popping the nodes gives the reversed order of that group.
After popping each node, we attach it to the result list using a tail pointer. This makes the reversal logic simple because the stack handles the ordering, while we only need to reconnect nodes one by one.
Algorithm
Create a dummy node and initialize a
tailpointer to build the result list, as the dummy node provides a fixed starting point whiletailtracks the end of the reversed groups.Traverse the linked list group by group, since each group of at most
knodes needs to be reversed independently.For each group, push at most
knodes into a stack, as the stack's LIFO property will provide the nodes in reverse order when they are removed.Pop the nodes from the stack one by one and attach each node after
tail, which places the group into reversed order in the result list.Move
tailforward after every attachment, so it always points to the last node currently present in the result list.Continue until all groups have been processed, including the final group when it contains fewer than
knodes.Set
tail->nexttoNULL, as the final node of the result list should not retain any old connection from the original list.Return
dummy->nextas the head of the updated linked list, since the dummy node is only used to simplify result construction.
Dry Run
rev ll in k grp stack
Solution
#include <bits/stdc++.h>using namespace std;class Node {public: int data; Node* next; Node(int value) { data = value; next = nullptr; }};class Solution {public: // Reverses nodes of a linked list in groups of size k using a stack Node* reverseKGroup(Node* head, int k) { // Base case: No transformation required for empty lists or groups of 1 if (head == nullptr || k <= 1) { return head; } Node* dummy = new Node(0); Node* tail = dummy; Node* current = head; while (current != nullptr) { stack<Node*> st; int count = 0; // Collect up to k nodes into the stack container while (current != nullptr && count < k) { st.push(current); current = current->next; count++; } // Pop nodes from the stack to reconstruct the group in reverse order while (!st.empty()) { tail->next = st.top(); st.pop(); tail = tail->next; } } // Set the final pointer to null to avoid circular list configurations tail->next = nullptr; return dummy->next; }};Node* buildList(vector<int>& values) { Node* dummy = new Node(0); Node* tail = dummy; for (int value : values) { tail->next = new Node(value); tail = tail->next; } return dummy->next;}void printList(Node* head) { Node* current = head; while (current != nullptr) { cout << current->data; if (current->next != nullptr) { cout << " "; } current = current->next; } cout << endl;}/* Driver code entry point */int main() { vector<int> values = {1, 2, 3, 4, 5, 6}; int k = 3; Node* head = buildList(values); Solution solution; Node* answer = solution.reverseKGroup(head, k); printList(answer); return 0;}Time Complexity: O(N), every node is pushed and popped once.
Space Complexity: O(K), stack stores at most k nodes at a time.
Better Approach
In this approach, recursion processes the linked list one group at a time. For every recursive call, we first check whether at least k nodes are available. If fewer than k nodes remain, the current head is returned without changing the remaining nodes.
When a complete group exists, its first k nodes are reversed by updating their links. The original head of the group becomes its tail after reversal. This tail is connected to the result returned by the recursive call for the remaining linked list.
The recursion handles the connection between consecutive reversed groups, making the solution concise while still reversing the nodes in place.
Algorithm
Check whether at least
knodes are available from the currenthead, as a group should be reversed only when it containsknodes.Return the current
headwhen fewer thanknodes remain, since the final incomplete group should stay unchanged.Reverse the first
knodes usingprev,current, andfrontpointers, wherefrontpreserves the remaining list before the current link is reversed.Recursively reverse the linked list starting after the current group, as the remaining groups can be processed using the same logic.
Connect the original group
headto the head returned by recursion, since the original head becomes the tail after the firstknodes are reversed.Return the new head of the reversed group, which is the last node among the original first
knodes.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Node {public: int data; Node* next; // Create a linked list node. Node(int value) { data = value; next = nullptr; }};class Solution {public: // Reverse nodes of a linked list in groups of size k recursively. Node* reverseKGroup(Node* head, int k) { if (head == nullptr || k <= 1) { return head; } Node* temp = head; // Check whether a complete group of k nodes exists. for (int i = 0; i < k; i++) { if (temp == nullptr) { return head; } temp = temp->next; } Node* previous = nullptr; Node* current = head; // Reverse the current group of k nodes. for (int i = 0; i < k; i++) { Node* front = current->next; current->next = previous; previous = current; current = front; } // Connect the current reversed group with the remaining groups. head->next = reverseKGroup(current, k); return previous; }};// Build a linked list from values.Node* buildList(vector<int>& values) { Node* dummy = new Node(0); Node* tail = dummy; for (int value : values) { tail->next = new Node(value); tail = tail->next; } return dummy->next;}// Print a linked list.void printList(Node* head) { Node* current = head; while (current != nullptr) { cout << current->data; if (current->next != nullptr) { cout << " "; } current = current->next; }}// Driver code.int main() { vector<int> values = {1, 2, 3, 4, 5, 6}; int k = 3; Node* head = buildList(values); Solution solution; Node* answer = solution.reverseKGroup(head, k); printList(answer); return 0;}Time Complexity: O(N), because every node is visited a constant number of times during group checking and reversal.
Space Complexity: O(N / K), because the recursion stack contains one call for each complete group of size k.
Optimal Approach
In this approach, we reverse every complete group of size k directly by changing links, without using any extra stack. For each group, we first locate the kth node to confirm that a complete group exists.
Once the kth node is found, we store the head of the next group before detaching the current group. The current group is then reversed using the standard linked list reversal technique. After reversal, the new group head is connected to the previously processed part of the list.
The original head of the group becomes the tail after reversal, so it is used as the connector for the next group. This keeps the reversal in-place and uses constant extra space.
Algorithm
Initialize
tempasheadandpreviousLastasNULL.For each group, locate the kth node starting from
temp.If fewer than
knodes remain, connectpreviousLastto the remaining nodes and stop.Store the next group head as
kthNode->next, then detach the current group by settingkthNode->next = NULL.Reverse the detached group using standard linked list reversal.
If this is the first group, update
head; otherwise, connectpreviousLast->nextto the new group head.Move
previousLastto the old group head, movetempto the next group head, and return the updatedheadafter all groups are processed.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Node {public: int data; Node* next; // Create a linked list node. Node(int value) { data = value; next = nullptr; }};class Solution {private: // Return the kth node starting from a given node. Node* getKthNode(Node* current, int k) { while (current != nullptr && k > 1) { current = current->next; k--; } return current; } // Reverse a detached linked list segment. Node* reverseList(Node* head) { Node* previous = nullptr; Node* current = head; while (current != nullptr) { Node* front = current->next; current->next = previous; previous = current; current = front; } return previous; }public: // Reverse nodes of a linked list in groups of size k in-place. Node* reverseKGroup(Node* head, int k) { if (head == nullptr || k <= 1) { return head; } Node* temp = head; Node* previousLast = nullptr; while (temp != nullptr) { // Locate the kth node of the current group. Node* kthNode = getKthNode(temp, k); if (kthNode == nullptr) { if (previousLast != nullptr) { previousLast->next = temp; } break; } // Store the next group head before detaching the segment. Node* nextNode = kthNode->next; kthNode->next = nullptr; // Reverse the detached group. reverseList(temp); if (temp == head) { head = kthNode; } else { previousLast->next = kthNode; } // Connect the reversed group tail with the next group. previousLast = temp; temp = nextNode; } return head; }};// Build a linked list from values.Node* buildList(vector<int>& values) { Node* dummy = new Node(0); Node* tail = dummy; for (int value : values) { tail->next = new Node(value); tail = tail->next; } return dummy->next;}// Print a linked list.void printList(Node* head) { Node* current = head; while (current != nullptr) { cout << current->data; if (current->next != nullptr) { cout << " "; } current = current->next; }}// Driver code.int main() { vector<int> values = {1, 2, 3, 4, 5, 6}; int k = 3; Node* head = buildList(values); Solution solution; Node* answer = solution.reverseKGroup(head, k);Time Complexity: O(N), every node is visited a constant number of times across group lookup and reversal.
Space Complexity: O(1), only pointer variables are used.
Interview follow-up Questions
Many platforms use a variant where the last incomplete group remains unchanged. The standard version reverses every group formed during traversal, and a single-node final group naturally looks unchanged.
Be the first to add a comment.