# Reverse Nodes in Even Length Groups
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reverse-nodes-in-even-length-groups)
Canonical: https://scaleengineer.com/dsa/problems/reverse-nodes-in-even-length-groups
**Data structures:** Linked List
**Companies:** [Zopsmart](https://scaleengineer.com/companies/zopsmart)
---
## Problem
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 `1st` node is assigned to the first group.
* The `2nd` and the `3rd` nodes are assigned to the second group.
* The `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:**

![](https://assets.glich.co/dsa/reverse-nodes-in-even-length-groups/image0.png) 

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

![](https://assets.glich.co/dsa/reverse-nodes-in-even-length-groups/image1.png) 

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

![](https://assets.glich.co/dsa/reverse-nodes-in-even-length-groups/image2.png) 

**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, 105]`.
* `0 <= Node.val <= 105`

# Approaches
## Using Auxiliary Array
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.
**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`.
**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.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 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) {
        if (head == null) {
            return null;
        }

        // 1. Convert linked list to ArrayList
        List<Integer> values = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            values.add(current.val);
            current = current.next;
        }

        int n = values.size();
        int groupLen = 1;
        int i = 0;

        // 2. Process groups in the ArrayList
        while (i < n) {
            int remaining = n - i;
            int currentGroupLen = Math.min(groupLen, remaining);

            if (currentGroupLen % 2 == 0) {
                // Reverse the sublist for the even length group
                int left = i;
                int right = i + currentGroupLen - 1;
                while (left < right) {
                    int temp = values.get(left);
                    values.set(left, values.get(right));
                    values.set(right, temp);
                    left++;
                    right--;
                }
            }

            i += groupLen;
            groupLen++;
        }

        // 3. Update the original linked list with modified values
        current = head;
        int j = 0;
        while (current != null) {
            current.val = values.get(j++);
            current = current.next;
        }

        return head;
    }
}
```
### 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`.

## One-Pass In-place Reversal
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.
**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.
**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.
### Explanation
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.

```java
/**
 * 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) {
        ListNode dummy = new ListNode(0, head);
        ListNode groupPrev = dummy;
        int groupLen = 1;

        while (groupPrev.next != null) {
            ListNode groupTail = groupPrev;
            int actualLen = 0;
            // Find the end of the current group and its actual length
            for (int i = 0; i < groupLen && groupTail.next != null; i++) {
                groupTail = groupTail.next;
                actualLen++;
            }

            if (actualLen % 2 == 0) {
                ListNode groupStart = groupPrev.next;
                ListNode nextGroupStart = groupTail.next;
                
                // Reverse the sublist in-place
                ListNode prev = null;
                ListNode curr = groupStart;
                ListNode tempTail = nextGroupStart;
                for (int i = 0; i < actualLen; i++) {
                    ListNode nextTemp = curr.next;
                    curr.next = tempTail;
                    tempTail = curr;
                    curr = nextTemp;
                }
                
                // Reconnect the list
                groupPrev.next = tempTail; // tempTail is the new head
                groupPrev = groupStart; // The original start is now the tail
            } else {
                // Move groupPrev to the end of the odd length group
                groupPrev = groupTail;
            }
            
            groupLen++;
        }
        return dummy.next;
    }
}
```
### 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`.

# Solutions
### Java

```java
/** * 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 ; } }
```

### Python

```python
# 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
```