1
class Solution {
2
 public:
3
  // Function to reverse a linked list
4
  ListNode *reverseList(ListNode *head) {
5
    if (!head) return head;
6
    ListNode *prev = NULL;
7
    while (head) {
8
      ListNode *temp = head->next;
9
      head->next = prev;
10
      prev = head;
11
      head = temp;
12
    }
13

14
    return prev;
15
  }
16

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

22
    ListNode *prev = dummy;
23

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

29
      // Determining the length of the current group
30
      // Its maximum length can be equal to len
31
      int j = 1;
32
      while (j < len && tail && tail->next) {
33
        tail = tail->next;
34
        j++;
35
      }
36

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

40
      if ((j % 2) == 0) {
41
        // If even sized group is found
42
        // Reversing the group and setting prev and head appropriately
43
        tail->next = NULL;
44
        prev->next = reverseList(head);
45
        prev = head;
46
        head->next = nextHead;
47
        head = nextHead;
48
      } else {
49
        // If group is odd sized, then simply going towards the next group
50
        prev = tail;
51
        head = nextHead;
52
      }
53
    }
54

55
    // Returning the head
56
    return dummy->next;
57
  }
58
};