Reverse Nodes in k-Group

Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
k = 3

Reversed Linked List: 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8

#include <iostream>

// Definition for singly-linked list
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to get the length of the linked list
int getLength(ListNode* head) {
    int length = 0;
    ListNode* current = head;
    while (current != nullptr) {
        length++;
        current = current->next;
    }
    return length;
}

// Function to reverse a linked list from position left to position right
ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (head == nullptr || left == right) {
        return head; // Nothing to reverse or invalid input
    }

    // Create a dummy node to handle the case where left = 1
    ListNode* dummy = new ListNode(0);
    dummy->next = head;

    // Find the node at position (left - 1)
    ListNode* prev = dummy;
    for (int i = 1; i < left; ++i) {
        prev = prev->next;
    }

    // Find the node at position right
    ListNode* curr = prev->next;
    ListNode* end = curr;
    for (int i = left; i <= right; ++i) {
        end = end->next;
    }

    // Reverse the sublist from position left to position right
    while (curr != end) {
        ListNode* nextNode = curr->next;
        curr->next = end->next;
        end->next = curr;
        curr = nextNode;
    }

    // Connect the reversed sublist with the rest of the list
    prev->next = end;

    return dummy->next; // New head of the reversed sublist
}

// Function to reverse the linked list in k-groups
ListNode* reverseKGroup(ListNode* head, int k) {
    int length = getLength(head);
    int numGroups = length / k;

    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* prevGroupEnd = dummy;

    for (int i = 0; i < numGroups; ++i) {
        int left = i * k + 1;
        int right = left + k - 1;

        head = reverseBetween(head, left, right);
        prevGroupEnd->next = head;

        for (int j = 0; j < k; ++j) {
            prevGroupEnd = prevGroupEnd->next;
        }
    }

    return dummy->next;
}

// Function to print the linked list
void printLinkedList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->val << " -> ";
        current = current->next;
    }
    std::cout << "nullptr" << std::endl;
}

int main() {
    // Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = new ListNode(6);
    head->next->next->next->next->next->next = new ListNode(7);
    head->next->next->next->next->next->next->next = new ListNode(8);

    int k = 3;

    std::cout << "Original Linked List: ";
    printLinkedList(head);

    ListNode* reversedHead = reverseKGroup(head, k);

    std::cout << "Reversed Linked List: ";
    printLinkedList(reversedHead);

    return 0;
}