/* Problem: https://leetcode.com/problems/reverse-nodes-in-k-group/
 */

#include <iostream>
#include <vector>

//  Below ListNode definition is copied form problem
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) {}
};
// Above ListNode definition is copied from problem

std::ostream &operator<<(std::ostream &out, ListNode *node) {
  out << "{";
  while (node != nullptr) {
    out << node->val << ", ";
    node = node->next;
  }
  out << "}";
  return out;
  ;
}

ListNode *solution(ListNode *node, int k) {
  if (k == 1)
    return node;
  ListNode *previous_group_last_node = nullptr, *current_node = node,
           *head = node;
  while (current_node != nullptr) {
    ListNode *current_group_first_node = current_node;
    int group_nodes_count;
    for (group_nodes_count = 1; group_nodes_count < k; group_nodes_count++) {
      if (current_node->next == nullptr) {
        break;
      }
      current_node = current_node->next;
    }
    if (group_nodes_count == k) {
      ListNode *current_group_last_node = current_node,
               *next_group_first_node = current_node->next,
               *left = current_group_first_node, *right = left->next;
      if (head == node) {
        head = current_group_last_node;
      }
      while (right != next_group_first_node) {
        ListNode *tmp = right->next;
        right->next = left;
        left = right;
        right = tmp;
      }
      if (previous_group_last_node != nullptr) {
        previous_group_last_node->next = current_group_last_node;
      }
      previous_group_last_node = current_group_first_node;
      current_group_first_node->next = next_group_first_node;
      current_node = next_group_first_node;
    } else {
      break;
    }
  }
  return head;
}

ListNode *vector_to_list(std::vector<int> &&vec) {
  ListNode *head = nullptr;
  for (int i = vec.size() - 1; i >= 0; i--) {
    head = new ListNode(vec[i], head);
  }
  return head;
}

int main() {
  std::cout << solution(vector_to_list({1, 2, 3, 4, 5}), 2) << std::endl
            << solution(vector_to_list({1, 2, 3, 4, 5}), 3) << std::endl
            << solution(vector_to_list({1, 2, 3, 4, 5}), 4) << std::endl;
  ;
  return 0;
}