LeetCode 2074 - Reverse Nodes in Even Length Groups
This problem gives us a singly linked list and asks us to process the nodes in groups whose sizes follow the natural number sequence: - Group 1 contains 1 node - Group 2 contains 2 nodes - Group 3 contains 3 nodes - Group 4 contains 4 nodes - And so on However, the list may…
Difficulty: 🟡 Medium
Topics: Linked List
Solution
Problem Understanding
This problem gives us a singly linked list and asks us to process the nodes in groups whose sizes follow the natural number sequence:
- Group 1 contains 1 node
- Group 2 contains 2 nodes
- Group 3 contains 3 nodes
- Group 4 contains 4 nodes
- And so on
However, the list may end before a group reaches its intended size. The final group can therefore be smaller than expected.
For every group, we must determine its actual length. If the group length is even, we reverse the nodes inside that group. If the group length is odd, we leave the group unchanged.
The important detail is that only the nodes inside a single group are reversed. The relative order between groups must remain intact.
For example, consider:
[5,2,6,3,9,1,7,3,8,4]
The groups become:
[5]
[2,6]
[3,9,1]
[7,3,8,4]
The groups of lengths 2 and 4 are even, so we reverse only those groups:
[5]
[6,2]
[3,9,1]
[4,8,3,7]
Final result:
[5,6,2,3,9,1,4,8,3,7]
The constraints allow up to 10^5 nodes, which means we need an efficient linear-time solution. Any approach that repeatedly traverses large portions of the list or performs expensive array operations could become too slow.
Several edge cases are especially important:
- A list with only one node
- A final group whose size is smaller than expected
- Multiple consecutive even-length groups
- A final group with even length that still needs reversal
- Groups of size 1, which should never be reversed because 1 is odd
Because this is a linked list problem, careful pointer manipulation is critical. Incorrect reconnection after reversal can easily break the list structure.
Approaches
Brute Force Approach
A straightforward approach is to first copy all linked list values into an array.
Once we have the array, we can process groups by index ranges:
- Determine the current group boundaries
- Check whether the group length is even
- Reverse the corresponding subarray if needed
- After processing all groups, rebuild the linked list from the modified array
This works because arrays make reversing ranges very easy. However, this approach uses additional memory proportional to the number of nodes.
Although the time complexity remains linear overall, the extra memory usage is unnecessary because the problem can be solved directly on the linked list itself.
Optimal Approach
The optimal solution manipulates the linked list in place.
The key insight is that we only need to reverse groups whose actual size is even. While traversing the list, we can:
- Determine the actual length of the current group
- Reverse the group if its size is even
- Reconnect the reversed portion back into the main list
- Continue processing the next group
This avoids converting the list into another data structure and uses only constant extra space.
The challenge is careful pointer management:
- We must know where the current group starts
- We must know where it ends
- We must preserve the node after the group
- After reversal, we must reconnect all parts correctly
Because each node is visited only a constant number of times, the algorithm runs efficiently in linear time.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Convert to array, reverse ranges, rebuild list |
| Optimal | O(n) | O(1) | Reverse even groups directly in the linked list |
Algorithm Walkthrough
- Create a dummy node that points to the head of the list.
The dummy node simplifies pointer handling, especially when reversing groups near the beginning of the list.
2. Maintain a pointer called prev_group_tail.
This pointer always represents the node immediately before the current group.
3. Start with group size 1.
The intended group sizes increase sequentially as 1, 2, 3, 4, ....
4. Traverse forward to determine the actual size of the current group.
Since the list may end early, the actual group size may be smaller than the intended size. 5. Store:
- The first node of the group
- The node immediately after the group
These references are necessary for reconnecting the list later. 6. Check whether the actual group length is even.
If the size is odd, leave the group unchanged and simply move forward. 7. If the group length is even, reverse the group in place.
Use the standard linked list reversal technique:
- Maintain
prevandcurr - Reverse pointers one node at a time
- Stop once the entire group is reversed
- Reconnect the reversed group back into the list.
After reversal:
- The original group head becomes the tail
- The original group tail becomes the new head
We reconnect:
prev_group_tail.nextto the new head- New tail to the next group
- Move
prev_group_tailto the end of the processed group.
This prepares the algorithm for the next iteration. 10. Increase the intended group size by 1 and continue until all nodes are processed.
Why it works
The algorithm always processes exactly one contiguous group at a time. Before modifying any pointers, it identifies the group's boundaries and preserves the connection to the rest of the list.
If the group size is odd, the list structure remains unchanged.
If the group size is even, reversing only the nodes inside the group preserves the relative order of all other nodes. Because the algorithm reconnects the previous group and the next group correctly after reversal, the linked list remains valid throughout execution.
Since every node belongs to exactly one group and is processed once, the final list correctly reflects all required reversals.
Python Solution
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
prev_group_tail = dummy
group_size = 1
while prev_group_tail.next:
group_head = prev_group_tail.next
# Find actual group length
current = group_head
actual_length = 0
while current and actual_length < group_size:
current = current.next
actual_length += 1
next_group_head = current
# Reverse if group length is even
if actual_length % 2 == 0:
prev = next_group_head
curr = group_head
for _ in range(actual_length):
temp = curr.next
curr.next = prev
prev = curr
curr = temp
prev_group_tail.next = prev
prev_group_tail = group_head
else:
for _ in range(actual_length):
prev_group_tail = prev_group_tail.next
group_size += 1
return dummy.next
The implementation begins by creating a dummy node. This avoids special handling when the first reversible group appears near the front of the list.
The variable prev_group_tail always points to the node immediately before the current group. This makes reconnection straightforward after processing the group.
To determine the actual group length, the algorithm traverses up to group_size nodes or until the list ends. This correctly handles incomplete final groups.
If the group length is even, the algorithm performs an in-place linked list reversal. The variable prev starts at the node after the group so that the reversed group's tail automatically reconnects to the remainder of the list during reversal.
After reversal:
prevbecomes the new group headgroup_headbecomes the new group tail
The pointers are then reconnected correctly.
If the group length is odd, no reversal occurs, and the algorithm simply advances prev_group_tail across the group.
Finally, the group size increases for the next iteration.
Go Solution
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseEvenLengthGroups(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
prevGroupTail := dummy
groupSize := 1
for prevGroupTail.Next != nil {
groupHead := prevGroupTail.Next
// Find actual group length
current := groupHead
actualLength := 0
for current != nil && actualLength < groupSize {
current = current.Next
actualLength++
}
nextGroupHead := current
// Reverse if even length
if actualLength%2 == 0 {
prev := nextGroupHead
curr := groupHead
for i := 0; i < actualLength; i++ {
temp := curr.Next
curr.Next = prev
prev = curr
curr = temp
}
prevGroupTail.Next = prev
prevGroupTail = groupHead
} else {
for i := 0; i < actualLength; i++ {
prevGroupTail = prevGroupTail.Next
}
}
groupSize++
}
return dummy.Next
}
The Go implementation follows the same logic as the Python version but uses Go pointer syntax.
A few implementation details are worth noting:
- Go uses
nilinstead of Python'sNone - Pointer manipulation is explicit through
*ListNode - The reversal loop uses a standard
forloop with an integer counter - No additional slices or arrays are allocated, so the algorithm maintains constant extra space usage
Because node values are limited to 10^5, integer overflow is not a concern in Go.
Worked Examples
Example 1
Input:
[5,2,6,3,9,1,7,3,8,4]
Initial grouping:
| Group | Nodes | Length | Action |
|---|---|---|---|
| 1 | [5] | 1 | Keep |
| 2 | [2,6] | 2 | Reverse |
| 3 | [3,9,1] | 3 | Keep |
| 4 | [7,3,8,4] | 4 | Reverse |
Step-by-step execution
Group 1
| Variable | Value |
|---|---|
| Intended size | 1 |
| Actual size | 1 |
| Even? | No |
List remains:
[5,2,6,3,9,1,7,3,8,4]
Group 2
| Variable | Value |
|---|---|
| Intended size | 2 |
| Actual size | 2 |
| Even? | Yes |
Before reversal:
[2,6]
After reversal:
[6,2]
List becomes:
[5,6,2,3,9,1,7,3,8,4]
Group 3
| Variable | Value |
|---|---|
| Intended size | 3 |
| Actual size | 3 |
| Even? | No |
List remains:
[5,6,2,3,9,1,7,3,8,4]
Group 4
| Variable | Value |
|---|---|
| Intended size | 4 |
| Actual size | 4 |
| Even? | Yes |
Before reversal:
[7,3,8,4]
After reversal:
[4,8,3,7]
Final result:
[5,6,2,3,9,1,4,8,3,7]
Example 2
Input:
[1,1,0,6]
Groups:
| Group | Nodes | Length | Action |
|---|---|---|---|
| 1 | [1] | 1 | Keep |
| 2 | [1,0] | 2 | Reverse |
| 3 | [6] | 1 | Keep |
After reversing group 2:
[1,0,1,6]
Example 3
Input:
[1,1,0,6,5]
Groups:
| Group | Nodes | Length | Action |
|---|---|---|---|
| 1 | [1] | 1 | Keep |
| 2 | [1,0] | 2 | Reverse |
| 3 | [6,5] | 2 | Reverse |
After group 2:
[1,0,1,6,5]
After group 3:
[1,0,1,5,6]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each node is visited a constant number of times |
| Space | O(1) | Only pointer variables are used |
The algorithm processes the linked list sequentially. Every node is traversed during group detection, and nodes in even groups are additionally visited during reversal. However, each node participates in only a constant amount of work overall, so the total runtime remains linear.
No auxiliary arrays, stacks, or hash maps are used. The algorithm only stores a few pointer variables, so the extra space complexity is constant.
Test Cases
# Helper functions
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build_list(values):
dummy = ListNode()
current = dummy
for value in values:
current.next = ListNode(value)
current = current.next
return dummy.next
def list_to_array(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
# Example 1
head = build_list([5,2,6,3,9,1,7,3,8,4])
result = Solution().reverseEvenLengthGroups(head)
assert list_to_array(result) == [5,6,2,3,9,1,4,8,3,7] # standard mixed groups
# Example 2
head = build_list([1,1,0,6])
result = Solution().reverseEvenLengthGroups(head)
assert list_to_array(result) == [1,0,1,6] # even middle group
# Example 3
head = build_list([1,1,0,6,5])
result = Solution().reverseEvenLengthGroups(head)
assert list_to_array(result) == [1,0,1,5,6] # incomplete final even group
# Single node
head = build_list([1])
result = Solution().reverseEvenLengthGroups(head)
assert list_to_array(result) == [1] # minimum size input
# Two nodes
head = build_list([1,2])
result = Solution().reverseEvenLengthGroups(head)
assert list_to_array(result) == [1,2] # second group incomplete with size 1
# Three nodes
head = build_list([1,2,3])
result = Solution().reverseEvenLengthGroups(head)
assert list_to_array(result) == [1,3,2] # second group reversed
# Four nodes
head = build_list([1,2,3,4])
result = Solution().reverseEvenLengthGroups(head)
assert list_to_array(result) == [1,3,2,4] # final single node unchanged
# Final group odd length
head = build_list([1,2,3,4,5,6])
result = Solution().reverseEvenLengthGroups(head)
assert list_to_array(result) == [1,3,2,4,5,6] # odd final group remains
# Final group even length
head = build_list([1,2,3,4,5])
result = Solution().reverseEvenLengthGroups(head)
assert list_to_array(result) == [1,3,2,5,4] # final group reversed
# Larger case
head = build_list([1,2,3,4,5,6,7,8,9,10,11,12])
result = Solution().reverseEvenLengthGroups(head)
assert list_to_array(result) == [1,3,2,4,5,6,10,9,8,7,11,12] # multiple reversals
| Test | Why |
|---|---|
[5,2,6,3,9,1,7,3,8,4] |
Standard example with multiple even groups |
[1,1,0,6] |
Tests reversal of a middle group |
[1,1,0,6,5] |
Tests incomplete final even group |
[1] |
Minimum input size |
[1,2] |
Final group smaller than intended |
[1,2,3] |
Smallest case with actual reversal |
[1,2,3,4] |
Ensures trailing odd group remains unchanged |
[1,2,3,4,5,6] |
Tests odd-sized final group |
[1,2,3,4,5] |
Tests even-sized final group |
[1,2,3,4,5,6,7,8,9,10,11,12] |
Larger mixed-case traversal |
Edge Cases
Single-node list
A list containing only one node is the smallest valid input. The first group has length 1, which is odd, so no reversal should occur.
This case can expose bugs where pointer traversal assumes additional nodes exist. The implementation handles it safely because the traversal loop stops immediately after processing the first node.
Final incomplete group
The final group may contain fewer nodes than its intended size. For example:
[1,2,3,4,5]
The intended groups are:
1
2
3
But only two nodes remain for the final group.
A buggy implementation might incorrectly assume the group size is always the intended size rather than the actual remaining size. The solution explicitly counts the real number of available nodes before deciding whether to reverse.
Consecutive even-length reversals
Some inputs contain multiple even groups close together. Incorrect reconnection logic can easily lose nodes or create cycles.
For example:
[1,1,0,6,5]
Both the second and third groups are even-sized and require reversal.
The implementation avoids pointer corruption by always preserving:
- The node before the group
- The node after the group
- The original group head
This guarantees correct reconnection after every reversal operation.