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.

&nbsp;
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.


&nbsp;
Constraints:


	The number of nodes in the list is in the range [1, 105].
	0 &lt;= Node.val &lt;= 105


class Solution:
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        group = 2
        tail = head # tail of previous group
        while tail and tail.next:
            cnt = 1 # actual size of the current group
            cur = tail.next # first node of the current group
            while cur.next and cnt < group:
                cur = cur.next
                cnt += 1
            pre, cur = tail, tail.next
            if cnt % 2 == 0: # if group size is even
                while cnt and cur:
                    nxt = cur.next
                    cur.next = pre
                    pre = cur
                    cur = nxt
                    cnt -= 1
                first = tail.next # first node of the original group
                first.next = cur
                tail.next = pre
                tail = first
            else:
                while cnt and cur:
                    pre, cur = cur, cur.next
                    cnt -= 1
                tail = pre
            group += 1
        return head
// This Question can be solved easily using two standard methods of LinkedList
// 1) addFirst (it adds node in front of the LinkedList)
// 2) addLast (it adds node in end of the LinkedList)

class Solution {

    static ListNode oh;
    static ListNode ot;
    static ListNode th;
    static ListNode tt;

    public ListNode reverseEvenLengthGroups(ListNode head) {

        oh = null;
        ot = null;
        th = null;
        tt = null;

        if(head == null || head.next == null)
            return head;

        int size = length(head);
        int idx = 1;
        ListNode curr = head;
        int group = 1;

        while(curr!=null)
        {
            int temp = size - idx + 1;
            if((temp>=group && group%2 == 0) || (temp<group && temp%2 == 0))
            {
                int k = group;
                while(k-->0 && curr!=null)
                {
                    ListNode t = curr.next;
                    curr.next = null;
                    addFirst(curr);
                    curr = t;
                    idx++;
                }
            }
            else
            {
                int k = group;
                while(k-->0 && curr!=null)
                {
                    ListNode t = curr.next;
                    curr.next = null;
                    addLast(curr);
                    curr = t;
                    idx++;
                }
            }

            if(oh==null && ot==null)
            {
                oh = th;
                ot = tt;
            }
            else
            {
                ot.next = th;
                ot = tt;
            }

            th = null;
            tt = null;
            group++;
        }

        return oh;
    }

    public int length (ListNode head)
    {
        if(head==null) return 0;
        ListNode curr = head;
        int k = 0;
        while(curr!=null)
        {
             k++;
            curr = curr.next;
        }
        return k;
    }

    public void addFirst(ListNode head)
    {
        if(tt == null && th == null)
        {
            th = head;
            tt = head;
        }
        else
        {
            head.next = th;
            th = head;
        }
    }

    public void addLast(ListNode head)
    {
        if(tt == null && th == null)
        {
            th = head;
            tt = head;
        }
        else
        {
            tt.next = head;
            tt = head;
        }
    }
}
class Solution {
public:

    // Function to reverse a linked list
    ListNode* reverseList(ListNode* head) {
        if(!head)
            return head;
        ListNode* prev = NULL;
        while(head) {
            ListNode* temp = head -> next;
            head -> next = prev;
            prev = head;
            head = temp;
        }

        return prev;
    }

    ListNode* reverseEvenLengthGroups(ListNode* head) {
        // Creating a dummy node to avoid adding checks for the first node
        ListNode* dummy = new ListNode();
        dummy -> next = head;

        ListNode* prev = dummy;

        // Loop to determine the lengths of groups
        for(int len = 1; len < 1e5 && head; len++) {
            ListNode* tail = head;
            ListNode* nextHead;

            // Determining the length of the current group
            // Its maximum length can be equal to len
            int j = 1;
            while(j < len && tail && tail -> next) {
                tail = tail -> next;
                j++;
            }

            // Head of the next group
            nextHead = tail -> next;

            if((j % 2) == 0) {
                // If even sized group is found
                // Reversing the group and setting prev and head appropriately
                tail -> next = NULL;
                prev -> next = reverseList(head);
                prev = head;
                head -> next = nextHead;
                head = nextHead;
            } else {
                // If group is odd sized, then simply going towards the next group
                prev = tail;
                head = nextHead;
            }
        }

        // Returning the head
        return dummy -> next;
    }
};
var reverseEvenLengthGroups = function(head) {
    let groupSize = 2;

    let start = head;

    let prev = head;
    let curr = head.next;

    let count = 0;
    
    while (curr != null) {
        if (count === groupSize) {
            if (groupSize % 2 === 0) { // we only reverse when it is even
                const end = curr;
                const tail = start.next; // the starting node of the reverse linked list will be the tail after the reverse takes place
                reverseList(start, end, count); // we need to reverse everything in the middle of start and end 
                start = tail; // we set the new start to the end of the reversed linked list
            }
            else { // when groupSize is even we don't need to reverse, but need to set the new start to the prev node
                start = prev;
            }
            count = 0; // whenever we reached the group size we need to reset our count and up our groupSize
            ++groupSize;
        }
        else { // just a normal traversal when we haven't hit our groupSize
            prev = curr;        
            curr = curr.next;
            ++count;
        }
    }
   
    if (count % 2 === 0) { // in the case where we ended early on even count
         reverseList(start, null, count);
    }
    
    return head;
    
    
    function reverseList(start, end, count) {
        if (start.next == null) return start; // for case when we have a single node
        
        let prev = start;
        
        let curr = start.next;
        let tail = start.next;
        
        for (let i = 0; i < count; ++i) {
            const next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        start.next = prev;
        tail.next = end;
        
        return ;
    }
};
Reverse Nodes in Even Length Groups