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,
1st node is assigned to the first group.2nd and the 3rd nodes are assigned to the second group.4th, 5th, and 6th nodes 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:
[1, 105].0 <= Node.val <= 105Problem 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.
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.
Time Complexity: O(n log n)
Space Complexity: O(n) due to temporary arrays used for merging.
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.
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.
Python
Java
TypeScript
| 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 | — |
| 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 |
LeetCode 2074: Reverse Nodes in Even Length Groups • Engineering Digest • 2,814 views views
Watch 8 more video solutions →Practice Reverse Nodes in Even Length Groups with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor