1
class Solution {
2
  pair<ListNode *, ListNode *> get_rev_list(ListNode *root) {
3
    ListNode *tail = root;
4
    ListNode *curr = root, *temp, *prev = NULL;
5

6
    while (curr != NULL) {
7
      temp = curr->next;
8
      curr->next = prev;
9

10
      prev = curr;
11
      curr = temp;
12
    }
13

14
    return make_pair(prev, tail);
15
  }
16

17
 public:
18
  ListNode *reverseKGroup(ListNode *head, int k) {
19
    if (k == 1) return head;
20

21
    vector<pair<ListNode *, ListNode *>> store;
22

23
    ListNode *temp = head, *temp_head = head;
24
    int len = 0;
25

26
    while (temp != NULL) {
27
      len++;
28

29
      if (len == k) {
30
        ListNode *next_head = temp->next;
31
        temp->next = NULL;
32

33
        store.push_back(get_rev_list(temp_head));
34
        temp = next_head;
35
        len = 0;
36
        temp_head = next_head;
37
      } else
38
        temp = temp->next;
39
    }
40

41
    if (len == k) store.push_back(get_rev_list(temp_head));
42

43
    for (int i = 1; i < store.size(); i++) store[i - 1].second->next = store[i].first;
44

45
    if (len != k) store[store.size() - 1].second->next = temp_head;
46

47
    return store[0].first;
48
  }
49
};