Skip to main content
Talentd

Reverse Nodes in k-Group - Solution & Explanation

HardLinked ListRecursion23 min readAsked at: Amazon, Microsoft, Apple +24
Practice this problem

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]

Example 2:

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

 

Constraints:

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

 

Follow-up: Can you solve the problem in O(1) extra memory space?

Approach Overview

Problem Overview: You are given the head of a singly linked list and an integer k. Reverse the nodes of the list k at a time. If the number of remaining nodes is less than k, leave them as they are. Node values cannot be modified; only pointers can be changed.

This problem tests pointer manipulation on a linked list. The key challenge is reversing exactly k nodes at a time while reconnecting the reversed segments back into the original list.

Approach 1: Iterative Group Reversing (O(n) time, O(1) space)

Traverse the list and process it in fixed-size groups of k. First, check whether k nodes exist ahead using a pointer scan. If fewer than k nodes remain, stop and keep them unchanged. When a valid group is found, reverse the k nodes using the standard in-place linked list reversal technique: iterate through the group and redirect next pointers one by one.

After reversing a group, reconnect three parts: the previous group's tail, the new head of the reversed group, and the next group's starting node. A dummy node before the head simplifies edge cases where the first group gets reversed. This approach touches each node a constant number of times, giving O(n) time complexity and O(1) extra space. This is the most common production-style implementation.

Approach 2: Recursive Group Reversal (O(n) time, O(n/k) recursion stack)

The recursive approach treats the list as repeating blocks of size k. First verify that k nodes exist. If they do, reverse the first k nodes using an iterative reversal loop. After reversing the block, recursively process the remainder of the list starting from the (k+1)th node.

The original head of the block becomes the tail after reversal. Connect this node to the result returned by the recursive call. Each recursive frame processes exactly one block of size k, so the total work remains O(n). The recursion stack depth is about n/k, which gives O(n/k) auxiliary space.

This approach reads naturally because each call solves one block and delegates the rest. It is a good demonstration of recursion applied to pointer structures, though it uses extra stack space compared to the iterative version.

Recommended for interviews: The iterative group-reversal approach is typically expected. It demonstrates strong control over pointer manipulation, constant-space optimization, and careful handling of boundary conditions. Showing the recursive idea first can communicate conceptual clarity, but the iterative solution proves you can implement an optimal O(n) and O(1) solution.

Approach 1: Iterative Group Reversing

Use an iterative approach to reverse each group of k nodes separately. This approach leverages an auxiliary dummy node and previous and current pointers to manage the connections at each step. We traverse the list, checking for complete sets of k nodes to reverse them. If a group of nodes has less than k nodes, leave them as they are.

We count length of the list to check if a full k group exists. A dummy node facilitates manipulation of edge connections. For each complete k-length, we perform a series of node swaps. We adjust prev, current, and next pointers accordingly to achieve the reversal.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes in the list, as each node is processed once.
Space Complexity: O(1), since no extra space is used apart from pointers.

Try this approach in the editor →

Approach 2: Recursive Group Reversal

Recurse through the linked list, reversing k nodes at a time. If a full group of k nodes is found, reverse and connect through recursive calls. Terminate when fewer than k nodes are left. This approach inherently uses the call stack for management of reverse sequences.

This recursive function inclusively reverses k nodes using a helper function and connects subsequent recursions via the next pointer. The recursion unwinds back, each time ending with any remaining nodes less than k in original order.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), since we process each node once even recursively.
Space Complexity: O(n/k), the recursion depth in worst case equals the number of complete k-sized groups.

Try this approach in the editor →

Approach 3: Simulation

We can simulate the entire reversal process according to the problem description.

First, we define a helper function reverse to reverse a linked list. Then, we define a dummy head node dummy and set its next pointer to head.

Next, we traverse the linked list, processing k nodes at a time. If the remaining nodes are fewer than k, we do not perform the reversal. Otherwise, we extract k nodes and call the reverse function to reverse these k nodes. Then, we connect the reversed linked list back to the original linked list. We continue to process the next k nodes until the entire linked list is traversed.

The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).

Code

PythonJavaGoTypeScriptRustC#PHP

Python

Java

Go

TypeScript

Rust

C#

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Group Reversing

Time Complexity: O(n), where n is the number of nodes in the list, as each node is processed once.
Space Complexity: O(1), since no extra space is used apart from pointers.

Recursive Group Reversal

Time Complexity: O(n), since we process each node once even recursively.
Space Complexity: O(n/k), the recursion depth in worst case equals the number of complete k-sized groups.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Group ReversingO(n)O(1)Best general solution. Constant extra space and commonly expected in interviews.
Recursive Group ReversalO(n)O(n/k)Useful when recursion makes the logic easier to express or when demonstrating recursive linked list manipulation.

Video Solution

L21. Reverse Nodes in K Group Size of LinkedList • take U forward • 286,294 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Reverse Nodes in k-Group easy or hard?
Reverse Nodes in k-Group is categorized as a hard problem because it requires careful pointer manipulation, handling partial groups, and maintaining correct connections between segments. The algorithm itself is linear, but implementing it without mistakes can be challenging.
Reverse Nodes in k-Group Python/Java solution
Both Python and Java solutions follow the same algorithm: iterate through the list, confirm k nodes exist, reverse the block using pointer updates, and reconnect it to the rest of the list. The logic remains identical across languages, with differences only in syntax and class definitions for the linked list node.
How to solve Reverse Nodes in k-Group in O(n)?
Process the linked list in groups of size k. For each group, first verify that k nodes exist, then reverse those k nodes using in-place pointer reversal. After reversing, connect the previous group's tail to the new head of the reversed block and continue scanning the list. This ensures each node is processed only a few times, giving O(n) time complexity.
What is the best approach for Reverse Nodes in k-Group?
The iterative group reversal approach is considered the best solution. It scans the list, reverses nodes in blocks of k using pointer manipulation, and reconnects the segments. This method runs in O(n) time and uses O(1) extra space, which is typically the optimal solution expected in interviews.
Is Reverse Nodes in k-Group asked at Google/Amazon/Meta?
Reverse Nodes in k-Group is a well-known hard linked list problem frequently discussed in interviews at large tech companies such as Amazon, Google, and Meta. Interviewers use it to evaluate pointer manipulation, edge case handling, and understanding of linked list operations.
What data structure is used in Reverse Nodes in k-Group?
The problem operates on a singly linked list. The solution relies on pointer manipulation to reverse segments of nodes and reconnect them correctly. No additional data structures are required in the optimal implementation.
What is the time complexity of Reverse Nodes in k-Group?
The optimal time complexity is O(n), where n is the number of nodes in the linked list. Each node is visited a constant number of times during group validation and reversal. The iterative approach achieves this with O(1) extra space, while the recursive version uses O(n/k) stack space.

Ready to solve this problem?

Practice Reverse Nodes in k-Group with our built-in code editor and test cases.

Practice on FleetCode
Previous

Reverse Nodes in Even Length Groups

Next

Swap Nodes in Pairs