2074. Reverse Nodes in Even Length Groups
Problem Description
The problem presents a scenario where we have a singly linked list, a data structure consisting of nodes, each with a value and a reference to the next node. The nodes in the list must be grouped according to the sequence of natural numbers i.e., the first node forms the first group, the next two nodes form the second group, the following three nodes form the third group, and so on. These groups' sizes increment by one, creating a naturally incremental grouping pattern across the linked list.
However, the issue involves a twist: we're asked to reverse the nodes only in those groups that have an even number of nodes. After executing these reversals, we need to return the new head of the modified linked list. It's crucial to notice that the last group's size may be smaller than or equal to the penultimate group, implying that the list may end before completing the size pattern of the sequence.
Intuition
The solution requires us to perform two primary operations:
- Identify the groups within the linked list that are of even length.
- Reverse the nodes in these even-length groups.
First, we note that the even-length groups are every other group, starting with the second one (sizes 2, 4, 6, etc.). To manage this, we can iterate through the list while keeping track of the current group size and the total nodes covered so far. Once we reach the end of a group, we reverse it if the group size is even, and then proceed to the next group.
For reversing a group of given size 'l' when present in the list, we temporarily detach this portion from the list, perform a standard linked list reversal, and then reconnect the reversed segment back to the main list.
To prevent issues with the final group (which may not conform to the natural number sequence if the list's length doesn't perfectly align with these group sizes), we check if there are enough nodes left for another group. If not, the remaining nodes form the last group, and we apply the even-length condition to decide if a reversal is needed.
The provided Python function reverseEvenLengthGroups
follows this approach, utilizing a nested reverse
helper function that specifically handles the reversal of 'l' nodes in the sublist it is given.
Lastly, to simplify handling edge cases such as the start and end of the list, a dummy node is employed, allowing for easy assignment and reference changes without additional null checks.
This approach requires updating node connections and occasionally counting nodes, both operations being O(1), making the entire algorithm run in O(n) time where n is the number of nodes in the list.
Learn more about Linked List patterns.
Solution Approach
The implementation employs a two-fold strategyāgroup detection and conditional reversalābased on simple list traversal and manipulation techniques.
To perform the list reversal operation, consider the reverse
helper function defined within the Solution
class. It takes two arguments: the head
of the sublist to be reversed and the length l
of the sublist. The function follows the classical linked list reversal approach:
- Initialize three pointers:
prev
(set toNone
),cur
(pointing to thehead
of the sublist), andtail
(also pointing to thehead
). These pointers help in reversing the links of the sublist while keeping track of its tail. - Iterate
i
from 0 tol - 1
. During each iteration, reverse the links by pointing the current node'snext
to its previous node (prev
). Then, updateprev
to the current node and movecur
to the next node in the original list. - Ensure the reversed sublist is reconnected to the main list by setting the
next
property of thetail
to the current nodecur
, which now points to the sublist's successor in the main list.
The main part of the solution is structured as follows:
- The initial step involves determining the total number of nodes
n
in the original list. This is done via a while-loop that traverses the list and increments a counter for each node encountered. - A
dummy
node is created with a value of 0 and itsnext
reference pointing to the head of the list. This is a common trick to simplify edge case handling in linked list problems, particularly when modifications near the head are required. - The actual traversal starts from the
dummy
node, using a pointerprev
that keeps track of the end of the last processed group. - The main while-loop executes as long as the starting index of the current group is within the bounds of the list. For each group iteration:
- If
l
is even, indicating an even-length group, call thereverse
function withprev.next
as the starting node of the group. Then, updateprev.next
with the returned node, which is the new head of the reversed group. - Independently of whether a group is reversed, a nested while-loop advances the
prev
pointerl
times forward, which is equivalent to skipping over the current group. - Increment the group size
l
by 1 for the next iteration.
- If
- Special attention is given for the last group, denoted by
left
. Ifleft
is even and greater than zero, it implies that the last group of nodes also needs to be reversed. The samereverse
function is called for this part.
Since the operations performed for each node are constant time, the overall time complexity of the solution is O(n), where n is the number of nodes in the linked list.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example:
Suppose we have the following linked list:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
According to the pattern described in the problem, the nodes should be grouped like so:
- Group 1:
1
- Group 2:
2 -> 3
(even-length, should be reversed) - Group 3:
4 -> 5 -> 6
- Group 4:
7
(End of the list; this would be the part of the next group if we had more nodes)
Following the steps outlined:
-
We start by determining the group sizes. The first group has a size of
1
, so it remains unchanged. The linked list still looks like this:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
. -
Next, we look at the second group which contains nodes
2
and3
. Since it's even-length, we need to reverse it. After the reversal, our linked list becomes:1 -> 3 -> 2 -> 4 -> 5 -> 6 -> 7
. -
We move on to the third group, which contains
4, 5, 6
. Since this group has an odd number of nodes (3
), we do not reverse them. The linked list remains:1 -> 3 -> 2 -> 4 -> 5 -> 6 -> 7
. -
Finally, we have the incomplete fourth group which would have had four members if the list were longer. Since it only contains
7
, and it's an odd-length group, we leave it as is.
Therefore, after applying the steps of the algorithm to the small example list, the modified linked list is:
1 -> 3 -> 2 -> 4 -> 5 -> 6 -> 7
From this example, we can see how the algorithm applies the group size pattern to decide where reversals are required and performs the reversal only on even-length groups using the reverse
helper function. The use of pointers like prev
, cur
, and tail
allows for the necessary list manipulations while traversing through the linked list only once, yielding an efficient O(n) time complexity.
Solution Implementation
1# Definition for singly-linked list.
2class ListNode:
3 def __init__(self, val=0, next_node=None):
4 self.val = val
5 self.next = next_node
6
7class Solution:
8 def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
9 # Helper function to reverse the linked list of a given length 'length'
10 def reverse(start, length):
11 previous, current = None, start
12 count = 0
13 while current and count < length:
14 temp = current.next
15 current.next = previous
16 previous = current
17 current = temp
18 count += 1
19 start.next = current
20 return previous
21
22 # Calculate the total number of nodes in the linked list
23 node_count = 0
24 temp_head = head
25 while temp_head:
26 temp_head = temp_head.next
27 node_count += 1
28
29 dummy = ListNode(0, head)
30 previous_group_end = dummy
31 group_size = 1
32
33 # Go through the list group by group
34 while (1 + group_size) * group_size // 2 <= node_count and previous_group_end:
35 # If the current group size is an even number, reverse the group
36 if group_size % 2 == 0:
37 previous_group_end.next = reverse(previous_group_end.next, group_size)
38
39 # Move the pointer to the end of the current group
40 for _ in range(group_size):
41 if previous_group_end:
42 previous_group_end = previous_group_end.next
43
44 # Increment the group size for the next iteration
45 group_size += 1
46
47 # Check if there are leftover nodes in the last group that form an even-length group
48 remaining_nodes = node_count - group_size * (group_size - 1) // 2
49 if remaining_nodes > 0 and remaining_nodes % 2 == 0:
50 previous_group_end.next = reverse(previous_group_end.next, remaining_nodes)
51
52 # Return the new head of the modified linked list
53 return dummy.next
54
1class Solution {
2 public ListNode reverseEvenLengthGroups(ListNode head) {
3 int n = 0;
4 // Calculate the total number of nodes in the linked list
5 for (ListNode node = head; node != null; node = node.next) {
6 n++;
7 }
8
9 // Dummy node to simplify reversal operations
10 ListNode dummy = new ListNode(0, head);
11 ListNode groupPrev = dummy;
12
13 // Group size starts from 1
14 int currentGroupSize = 1;
15 // Continue grouping and reversing while there are enough nodes remaining
16 while (((currentGroupSize + 1) * currentGroupSize) / 2 <= n && groupPrev != null) {
17 // Reverse the group if the size is even
18 if (currentGroupSize % 2 == 0) {
19 ListNode nextGroupHead = groupPrev.next;
20 groupPrev.next = reverse(nextGroupHead, currentGroupSize);
21 }
22
23 // Move the groupPrev pointer to the end of the current group
24 for (int i = 0; i < currentGroupSize && groupPrev != null; i++) {
25 groupPrev = groupPrev.next;
26 }
27
28 // Proceed to the next group
29 currentGroupSize++;
30 }
31
32 // Calculate the number of nodes left for the last group
33 int nodesLeft = n - currentGroupSize * (currentGroupSize - 1) / 2;
34 // Perform group reversal if the number of nodes left is even
35 if (nodesLeft > 0 && nodesLeft % 2 == 0) {
36 ListNode nextGroupHead = groupPrev.next;
37 groupPrev.next = reverse(nextGroupHead, nodesLeft);
38 }
39
40 // Return the head of the reversed list
41 return dummy.next;
42 }
43
44 /**
45 * Reverses a group of nodes in the linked list.
46 * @param head the head of the group to reverse
47 * @param groupSize the number of nodes to reverse
48 * @return new head of the reversed group
49 */
50 private ListNode reverse(ListNode head, int groupSize) {
51 ListNode prev = null;
52 ListNode current = head;
53 ListNode groupTail = current;
54 int count = 0;
55
56 // Perform reversal for groupSize nodes
57 while (current != null && count < groupSize) {
58 ListNode next = current.next;
59 current.next = prev;
60 prev = current;
61 current = next;
62 count++;
63 }
64
65 // Link the end of the reversed group to the rest of the list
66 groupTail.next = current;
67 return prev;
68 }
69}
70
1#include <vector>
2#include <algorithm>
3
4// Definition for singly-linked list.
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11// Function to reverse even length groups in a singly linked list.
12ListNode* reverseEvenLengthGroups(ListNode* head) {
13 // A vector to store the node values.
14 std::vector<int> nodeValues;
15 ListNode* currentNode = head;
16
17 // Traverse the linked list and collect node values.
18 while (currentNode != nullptr) {
19 nodeValues.push_back(currentNode->val);
20 currentNode = currentNode->next;
21 }
22
23 int totalNodes = nodeValues.size();
24 // Start processing groups.
25 for (int startIndex = 0, groupSize = 1; startIndex < totalNodes; startIndex += groupSize, groupSize++) {
26 // For the last group, adjust the size if it's shorter than expected.
27 groupSize = std::min(totalNodes - startIndex, groupSize);
28 // Check if the current group is of even length.
29 if (groupSize % 2 == 0) {
30 // Reverse the even length group.
31 std::reverse(nodeValues.begin() + startIndex, nodeValues.begin() + startIndex + groupSize);
32 }
33 }
34
35 // Reset the current node to the head of the list.
36 currentNode = head;
37 // Update the list nodes with the reordered values.
38 for (int value : nodeValues) {
39 if (currentNode != nullptr) {
40 currentNode->val = value; // Set value to the current node.
41 currentNode = currentNode->next; // Move to the next node.
42 }
43 }
44
45 // Return the modified linked list head.
46 return head;
47}
48
1// Function to reverse even length groups in a singly linked list.
2function reverseEvenLengthGroups(head: ListNode | null): ListNode | null {
3 // Node values are stored in this array.
4 let nodeValues: number[] = [];
5 let currentNode: ListNode | null = head;
6
7 // Traverse the linked list and collect node values.
8 while (currentNode) {
9 nodeValues.push(currentNode.val);
10 currentNode = currentNode.next;
11 }
12
13 const totalNodes: number = nodeValues.length;
14 // Start processing groups.
15 for (let startIndex = 0, groupSize = 1; startIndex < totalNodes; startIndex += groupSize, groupSize++) {
16 // For the last group, adjust the size if it's shorter than expected.
17 groupSize = Math.min(totalNodes - startIndex, groupSize);
18 // Check if the current group is of even length.
19 if (groupSize % 2 === 0) {
20 // Extract the subgroup of even length.
21 let subGroup: number[] = nodeValues.splice(startIndex, groupSize);
22 subGroup.reverse(); // Reverse the subgroup.
23 // Insert the reversed subgroup back into the node values array.
24 nodeValues.splice(startIndex, 0, ...subGroup);
25 }
26 }
27
28 // Reset the current node to the head of the list.
29 currentNode = head;
30 // Update the list nodes with the reordered values.
31 for (let value of nodeValues) {
32 if (currentNode) {
33 currentNode.val = value; // Set value to the current node.
34 currentNode = currentNode.next; // Move to the next node.
35 }
36 }
37
38 // Return the modified linked list head.
39 return head;
40}
41
Time and Space Complexity
Time Complexity
The given code consists of two main parts: first, finding the total number of nodes in the linked list, and second, reversing even-length groups.
-
Counting the nodes in the linked list has a time complexity of
O(n)
, wheren
is the total number of nodes. This is done with a simple while loop iterating through each node exactly once. -
The second part involves iterating over the list again and for each group potentially reversing the nodes. Each node is involved in at most one reverse operation. The worst-case scenario is when all groups but the last are of even length. In this case, each node is touched twice: once for the actual reversal and once more when iterating through the groups. This implies a time complexity of
O(2n)
for the worst case, simplified toO(n)
. -
The arithmetic calculation of
(1 + l) * l // 2
is constant time for each group, since it doesn't depend on the list's length directly, but on the count of groups.
Combining these parts, the overall time complexity is O(n + n)
, which simplifies to O(n)
.
Space Complexity
The space complexity is determined by the amount of extra space used by the algorithm, not counting the input linked list.
-
We have a fixed number of variables (
prev
,cur
,t
,tail
,n
,l
,dummy
, andleft
) and a fixed-size stack for our recursive call to reverse the list. However, since the reversing is done iteratively within a while loop and not recursively, the space complexity is not directly affected by the size of the input list. -
The
reverse
function uses a few temporary variables, but it does not allocate scaling additional space other than function call overhead, which is constant for each call since we are not using recursive calls.
Thus, the space complexity is O(1)
since it does not scale with the size of the input.
Overall, the code efficiently processes the list in linear time with constant extra space.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!