Reverse Nodes in Even Length Groups

Med

#1888Time: O(N), where N is the number of nodes. The conversion to an array takes O(N), processing the array takes O(N) (as each element is part of one reversal at most), and updating the list values takes another O(N). Total is O(N).Space: O(N) to store the node values in the `ArrayList`.1 company

Data structures

Linked List

Companies

Zopsmart

Prompt

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,

The 1^st node is assigned to the first group.
The 2^nd and the 3^rd nodes are assigned to the second group.
The 4^th, 5^th, and 6^th 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:

The number of nodes in the list is in the range [1, 10⁵].
0 <= Node.val <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simplifies the problem by converting the linked list into a more flexible data structure like an array or ArrayList. We first traverse the linked list and store all its node values. Then, we can easily access and manipulate groups of elements by their indices. After reversing the values of even-length groups within the array, we iterate through the original linked list again, updating each node's value from the modified array.

Algorithm

Create an ArrayList of integers.
Traverse the linked list from head to tail, adding each node's val to the ArrayList.
Initialize a group_len = 1 and start_index = 0.
Loop while start_index is less than the size of the list:
- Calculate the end_index for the current group: min(start_index + group_len, list_size).
- Calculate the actual_len of the group: end_index - start_index.
- If actual_len is even, reverse the sublist of the ArrayList from start_index to end_index - 1.
- Update start_index for the next group: start_index += group_len.
- Increment group_len.
Traverse the original linked list again, and for each node, update its val with the corresponding value from the modified ArrayList.
Return the original head.

Walkthrough

The core idea is to trade space for simplicity. By moving the data to an array, we get O(1) access to any element, which makes grouping and reversing sub-sections much easier than manipulating pointers in a linked list.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5/**6 * Definition for singly-linked list.7 * public class ListNode {8 *     int val;9 *     ListNode next;10 *     ListNode() {}11 *     ListNode(int val) { this.val = val; }12 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }13 * }14 */15class Solution {16    public ListNode reverseEvenLengthGroups(ListNode head) {17        if (head == null) {18            return null;19        }20 21        // 1. Convert linked list to ArrayList22        List<Integer> values = new ArrayList<>();23        ListNode current = head;24        while (current != null) {25            values.add(current.val);26            current = current.next;27        }28 29        int n = values.size();30        int groupLen = 1;31        int i = 0;32 33        // 2. Process groups in the ArrayList34        while (i < n) {35            int remaining = n - i;36            int currentGroupLen = Math.min(groupLen, remaining);37 38            if (currentGroupLen % 2 == 0) {39                // Reverse the sublist for the even length group40                int left = i;41                int right = i + currentGroupLen - 1;42                while (left < right) {43                    int temp = values.get(left);44                    values.set(left, values.get(right));45                    values.set(right, temp);46                    left++;47                    right--;48                }49            }50 51            i += groupLen;52            groupLen++;53        }54 55        // 3. Update the original linked list with modified values56        current = head;57        int j = 0;58        while (current != null) {59            current.val = values.get(j++);60            current = current.next;61        }62 63        return head;64    }65}

Complexity

Time

O(N), where N is the number of nodes. The conversion to an array takes O(N), processing the array takes O(N) (as each element is part of one reversal at most), and updating the list values takes another O(N). Total is O(N).

Space

O(N) to store the node values in the `ArrayList`.

Trade-offs

Pros

Simpler logic and implementation compared to in-place pointer manipulation.
Random access to elements makes sublist reversal straightforward.

Cons

Requires extra space proportional to the number of nodes in the list, which can be significant for large lists.
Involves three passes over the data (list to array, process array, array to list), whereas an in-place solution needs only one pass.

This is the optimal approach, modifying the linked list directly without using any significant extra storage. It involves a single pass through the list, where we identify groups, check their lengths, and perform reversals on the spot by carefully manipulating the next pointers of the nodes. This avoids the overhead of creating and populating an auxiliary data structure.

Algorithm

Use a group_prev pointer to mark the node just before the current group begins. To handle all cases uniformly, we can use a dummy node pointing to the head, so group_prev starts at the dummy node.
Initialize group_len = 1.
Iterate as long as there are nodes to process (group_prev.next != null).
In each iteration, find the tail of the current group, group_tail, and count its actual_len. Start from group_prev and advance a pointer group_len times or until the end of the list is reached.
If actual_len is even:
- The group to be reversed starts at group_prev.next and ends at group_tail.
- Perform a standard in-place reversal on this sublist.
- Carefully reconnect the pointers: group_prev should point to the new head of the reversed sublist (the original group_tail), and the new tail of the sublist (the original group_start) should point to the start of the next group.
- Update group_prev for the next iteration to be the new tail of the just-processed group.
If actual_len is odd:
- No reversal is needed.
- Simply advance group_prev to group_tail to prepare for the next group.
Increment group_len for the next iteration.
Return dummy.next.

Walkthrough

We iterate through the list, keeping track of the end of the previous group. For each new group, we first determine its actual size. If the size is even, we perform a standard sublist reversal. The key challenge is to correctly re-link the reversed sublist with the rest of the list. A dummy node is used to simplify the handling of the first group.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode reverseEvenLengthGroups(ListNode head) {13        ListNode dummy = new ListNode(0, head);14        ListNode groupPrev = dummy;15        int groupLen = 1;16 17        while (groupPrev.next != null) {18            ListNode groupTail = groupPrev;19            int actualLen = 0;20            // Find the end of the current group and its actual length21            for (int i = 0; i < groupLen && groupTail.next != null; i++) {22                groupTail = groupTail.next;23                actualLen++;24            }25 26            if (actualLen % 2 == 0) {27                ListNode groupStart = groupPrev.next;28                ListNode nextGroupStart = groupTail.next;29                30                // Reverse the sublist in-place31                ListNode prev = null;32                ListNode curr = groupStart;33                ListNode tempTail = nextGroupStart;34                for (int i = 0; i < actualLen; i++) {35                    ListNode nextTemp = curr.next;36                    curr.next = tempTail;37                    tempTail = curr;38                    curr = nextTemp;39                }40                41                // Reconnect the list42                groupPrev.next = tempTail; // tempTail is the new head43                groupPrev = groupStart; // The original start is now the tail44            } else {45                // Move groupPrev to the end of the odd length group46                groupPrev = groupTail;47            }48            49            groupLen++;50        }51        return dummy.next;52    }53}

Complexity

Time

O(N), where N is the number of nodes. Each node is visited a constant number of times during the single pass.

Space

O(1), as we only use a few pointers for manipulation, regardless of the list size.

Trade-offs

Pros

Highly efficient in terms of memory, using only a constant amount of extra space.
Processes the list in a single pass, making it time-efficient.

Cons

The pointer manipulation logic is complex and can be prone to off-by-one errors or incorrect linking.
Harder to read, debug, and maintain compared to the array-based solution.

Solutions

Solution

1/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseEvenLengthGroups ( ListNode head ) { int n = 0 ; for ( ListNode t = head ; t != null ; t = t . next ) { ++ n ; } ListNode dummy = new ListNode ( 0 , head ); ListNode prev = dummy ; int l = 1 ; for (; ( 1 + l ) * l / 2 <= n && prev != null ; ++ l ) { if ( l % 2 == 0 ) { ListNode node = prev . next ; prev . next = reverse ( node , l ); } for ( int i = 0 ; i < l && prev != null ; ++ i ) { prev = prev . next ; } } int left = n - l * ( l - 1 ) / 2 ; if ( left > 0 && left % 2 == 0 ) { ListNode node = prev . next ; prev . next = reverse ( node , left ); } return dummy . next ; } private ListNode reverse ( ListNode head , int l ) { ListNode prev = null ; ListNode cur = head ; ListNode tail = cur ; int i = 0 ; while ( cur != null && i < l ) { ListNode t = cur . next ; cur . next = prev ; prev = cur ; cur = t ; ++ i ; } tail . next = cur ; return prev ; } }

1# 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 ]: def reverse ( head , l ): prev , cur , tail = None , head , head i = 0 while cur and i < l : t = cur . next cur . next = prev prev = cur cur = t i += 1 tail . next = cur return prev n = 0 t = head while t : t = t . next n += 1 dummy = ListNode ( 0 , head ) prev = dummy l = 1 while ( 1 + l ) * l // 2 <= n and prev : if l % 2 == 0 : prev . next = reverse ( prev . next , l ) i = 0 while i < l and prev : prev = prev . next i += 1 l += 1 left = n - l * ( l - 1 ) // 2 if left > 0 and left % 2 == 0 : prev . next = reverse ( prev . next , left ) return dummy . next

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem