Given the head of a singly linked list and an integer k, reverse the nodes of the list k at a time and return the new head of the reversed linked list. If the number of nodes in the linked list is not a multiple of k, leave the remaining nodes as they are.

Example:

Input:

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

Output:

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

Explanation: In the input, the linked list is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8, and k = 3. After reversing the nodes in groups of 3, the new linked list becomes 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8.

Solution in C++:

#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;
}

Explanation:

  1. The reverseKGroup function takes the head of the linked list and an integer k as input and returns the new head of the reversed linked list in k-groups.
  2. We start by finding the total number of groups, numGroups, in the linked list based on the given value of k.
  3. We use a dummy node, dummy, to handle the case where k = 1 or head is nullptr.
  4. We use a for loop to reverse the linked list in k-groups. For each group, we find the left and right positions, and then reverse the sublist between these positions using the reverseBetween function from the previous solution.
  5. We update the previous group’s end node, prevGroupEnd, to point to the head of the newly reversed sublist.
  6. We continue this process until all numGroups are reversed.

Time Complexity:

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. The reverseBetween function is called for each group, and each group reversal takes linear time.

Space Complexity:

The space complexity of this solution is O(1) as we use a constant amount of additional space for variables. The reversal is done in-place without using any additional data structures.