// Reverse k node of linked list

// Assume have at least k knode

ListNode* reverseLinkedList(ListNode* head, int k) {

  ListNode *rev_head = nullptr;

  ListNode *ptr = head;

  while (k > 0) {

    ListNode *next_node = ptr->next;

    ptr->next = rev_head;

    rev_head = ptr;

    ptr = next_node;

    k--;

  }

  return rev_head;

}



ListNode* reverseKGroup(ListNode* head, int k) {

  int count = 0;

  ListNode* ptr = head;



  // Check if there is atleast k nodes left in the linked list

  while (count < k && ptr != nullptr) {

    ptr = ptr->next;

    count++;

  }



  // Reverse if we have k node

  if (count == k) {

    // Reverse first k node

    // Get the reverse list head

    auto reverseHead = reverseLinkedList(head, k);

    // Recurse on the remaing linked list

    head->next = reverseKGroup(ptr, k);

    return reverseHead;

  }

  return head;

}