Reverse Nodes in Even Length Groups - Solution & Explanation
Problem Statement
You are given the head of a linked list.
The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of the natural numbers (1, 2, 3, 4, ...). The length of a group is the number of nodes assigned to it. In other words,
- The
1stnode is assigned to the first group. - The
2ndand the3rdnodes are assigned to the second group. - The
4th,5th, and6thnodes are assigned to the third group, and so on.
Note that the length of the last group may be less than or equal to 1 + the length of the second to last group.
Reverse the nodes in each group with an even length, and return the head of the modified linked list.
Example 1:
Input: head = [5,2,6,3,9,1,7,3,8,4] Output: [5,6,2,3,9,1,4,8,3,7] Explanation: - The length of the first group is 1, which is odd, hence no reversal occurs. - The length of the second group is 2, which is even, hence the nodes are reversed. - The length of the third group is 3, which is odd, hence no reversal occurs. - The length of the last group is 4, which is even, hence the nodes are reversed.
Example 2:
Input: head = [1,1,0,6] Output: [1,0,1,6] Explanation: - The length of the first group is 1. No reversal occurs. - The length of the second group is 2. The nodes are reversed. - The length of the last group is 1. No reversal occurs.
Example 3:
Input: head = [1,1,0,6,5] Output: [1,0,1,5,6] Explanation: - The length of the first group is 1. No reversal occurs. - The length of the second group is 2. The nodes are reversed. - The length of the last group is 2. The nodes are reversed.
Constraints:
- The number of nodes in the list is in the range
[1, 105]. 0 <= Node.val <= 105
Approach Overview
Problem Overview: You are given the head of a singly linked list. Nodes are grouped sequentially with sizes 1, 2, 3, 4, and so on. If a group contains an even number of nodes, reverse that group in-place. Odd-length groups remain unchanged. The task is to process the entire list while maintaining correct group boundaries.
Approach 1: Divide and Conquer (O(n) time, O(n) recursion stack)
This approach treats each group as a subproblem. Traverse the list to determine the size of the current group, then isolate that segment. If the segment length is even, reverse it using the standard linked list reversal routine. Recursively process the remaining list and connect the results. The recursion naturally splits the list into independent segments and combines them after processing. Time complexity remains O(n) because each node is visited a constant number of times, while the recursion stack requires up to O(n) space in the worst case.
Approach 2: Greedy Algorithm (O(n) time, O(1) space)
The greedy strategy scans the list once while dynamically forming groups. Maintain a pointer to the start of the current group and track the intended group size (1, 2, 3, ...). Count how many nodes actually exist in the group since the final group may be smaller than expected. If the counted length is even, reverse that segment using the standard iterative reversal with three pointers (prev, curr, next). Otherwise, leave the segment unchanged and simply move forward. Because each node is visited and reversed at most once, the total runtime is O(n) with O(1) extra space.
The key detail is correctly handling the last group. If fewer nodes remain than the expected group size, treat the remaining nodes as the final group and check whether its actual length is even before deciding to reverse.
This problem is a classic exercise in linked list manipulation. Efficient implementations rely on pointer updates rather than extra memory. The greedy traversal also resembles two pointer style pointer management while applying conditional reversal logic similar to many greedy decisions.
Recommended for interviews: The greedy single-pass approach is what most interviewers expect. It demonstrates strong control over pointer manipulation, segment detection, and in-place reversal. The divide and conquer version shows conceptual clarity, but the iterative greedy solution highlights practical linked list mastery and optimal space usage.
Approach 1: Divide and Conquer
In this approach, we tackle the problem by dividing it into smaller sub-problems, solving each sub-problem individually, and then combining their results to get the final solution. This commonly applies in problems where operations are more manageable on smaller datasets or when using recursive strategies such as mergesort, quicksort, or binary search. The efficiency depends on how well we can split the problem and merge the results.
This C solution implements the Merge Sort algorithm using a divide-and-conquer strategy. We recursively divide the array and merge sorted halves, utilizing helper arrays to facilitate the merging process. It's a highly efficient approach for sorting with a logarithmic depth recursion.
Complexity
Time Complexity: O(n log n)
Space Complexity: O(n) due to temporary arrays used for merging.
Approach 2: Greedy Algorithm
Greedy algorithms build a solution piece by piece, always choosing the next piece that offers the most immediate benefit. It doesn't pause to reconsider its previous choices, which can sometimes lead to suboptimal solutions, but they can be very effective for problems like coin change or activity selection where local optimizations lead to global solutions.
This C code snippet demonstrates a greedy algorithm to find the minimum number of coins required for a given value. Starting with the highest denomination coin, it subtracts as much as possible until the target value is met.
Complexity
Time Complexity: O(V/d), where V is the value and d is the denomination.
Space Complexity: O(1), since only a few integers are used for storage.
Approach 3: Default Approach
Code
Python
Java
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Divide and Conquer | Time Complexity: O(n log n) |
| Greedy Algorithm | Time Complexity: O(V/d), where V is the value and d is the denomination. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer | O(n) | O(n) | When recursion simplifies reasoning about independent linked list segments |
| Greedy Iterative Reversal | O(n) | O(1) | Best general solution; optimal for interviews and memory‑constrained environments |
Video Solution
LeetCode 2074: Reverse Nodes in Even Length Groups • Engineering Digest • 3,256 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reverse Nodes in Even Length Groups easy or hard?
Reverse Nodes in Even Length Groups Python/Java solution
How to solve Reverse Nodes in Even Length Groups in O(n)?
What is the best approach for Reverse Nodes in Even Length Groups?
Is Reverse Nodes in Even Length Groups asked at Google/Amazon/Meta?
What data structure is used in Reverse Nodes in Even Length Groups?
What is the time complexity of Reverse Nodes in Even Length Groups?
Ready to solve this problem?
Practice Reverse Nodes in Even Length Groups with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor