2074. Reverse Nodes in Even Length Groups

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.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    ListNode* cut(ListNode* head, int req) {
        ListNode* runner = head;
        while(runner->next and --req) {
            runner = runner->next;
        }
        return runner;
    }
    int sizeOf(ListNode* node) {
        int res = 0;
        ListNode* runner = node;
        while(runner) {
            runner = runner->next;
            res++;
        }
        return res;
    }
    ListNode* reverse(ListNode* node) {
        ListNode* head = node;
        while(node->next) {
            ListNode* next = node->next;
            node->next = next->next;
            next->next = head;
            head = next;
        }
        return head;
    }
    void connect(ListNode* A, ListNode* B) {
        ListNode* runner = A;
        while(runner->next) runner = runner->next;
        runner->next = B;
    }
public:
    ListNode* reverseEvenLengthGroups(ListNode* head) {
        int size = 1;
        ListNode* runner = head;
        vector<ListNode*> nodes;
        while(runner) {
            nodes.push_back(runner);
            auto tail = cut(runner,size++);
            runner = tail->next;
            tail->next = nullptr;
        }
        for(int i = 0; i < nodes.size(); i++) {
            int size = sizeOf(nodes[i]);
            if(size & 1) continue;
            nodes[i] = reverse(nodes[i]);
        }
        for(int i = 0; i < nodes.size() - 1; i++) {
            connect(nodes[i], nodes[i + 1]);
        }
        return nodes[0];
    }
};