Watch 9 video solutions for Reverse Nodes in Even Length Groups, a medium level problem involving Linked List. This walkthrough by Engineering Digest has 2,814 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |