2074. Reverse Nodes in Even Length Groups

MediumLinked List
Leetcode Link

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:

  1. Identify the groups within the linked list that are of even length.
  2. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

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:

  1. Initialize three pointers: prev (set to None), cur (pointing to the head of the sublist), and tail (also pointing to the head). These pointers help in reversing the links of the sublist while keeping track of its tail.
  2. Iterate i from 0 to l - 1. During each iteration, reverse the links by pointing the current node's next to its previous node (prev). Then, update prev to the current node and move cur to the next node in the original list.
  3. Ensure the reversed sublist is reconnected to the main list by setting the next property of the tail to the current node cur, 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 its next 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 pointer prev 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 the reverse function with prev.next as the starting node of the group. Then, update prev.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 pointer l times forward, which is equivalent to skipping over the current group.
    • Increment the group size l by 1 for the next iteration.
  • Special attention is given for the last group, denoted by left. If left is even and greater than zero, it implies that the last group of nodes also needs to be reversed. The same reverse 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Example 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:

  1. 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.

  2. Next, we look at the second group which contains nodes 2 and 3. Since it's even-length, we need to reverse it. After the reversal, our linked list becomes: 1 -> 3 -> 2 -> 4 -> 5 -> 6 -> 7.

  3. 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.

  4. 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
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

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.

  1. Counting the nodes in the linked list has a time complexity of O(n), where n is the total number of nodes. This is done with a simple while loop iterating through each node exactly once.

  2. 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 to O(n).

  3. 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.

  1. We have a fixed number of variables (prev, cur, t, tail, n, l, dummy, and left) 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.

  2. 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.

Fast Track Your Learning with Our Quick Skills Quiz:

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

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫