Reverse Nodes in k-Group - CPP Solution

1. Introduction

In this blog post, we tackle an advanced problem in linked list manipulation: reversing the nodes of a linked list k at a time. This problem tests the ability to traverse and modify linked lists in segments.

Problem

Given the head of a linked list, the task is to reverse every k nodes of the list. If the number of nodes is not a multiple of k, the remaining nodes at the end should be left as they are. The values of the nodes must not be altered; only the nodes themselves may be rearranged.

2. Solution Steps

1. Create a dummy node to simplify handling the head of the list.

2. Use two pointers: prev and curr, where prev initially points to the dummy node.

3. For each group of k nodes:

a. Check if there are k nodes available to reverse.

b. If yes, reverse the k nodes.

c. Update the connections between the reversed group and the rest of the list.

4. Continue until all groups are processed.

5. Return the next node of the dummy node as the new head of the list.

3. Code Program

#include <iostream>
using namespace std;

// Define the ListNode structure
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to reverse k nodes in the list
ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode *prev = &dummy, *curr = head;

    while (curr) {
        ListNode *tail = curr;
        int count = k;
        
        // Check if there are k nodes to reverse
        while (count && curr) {
            curr = curr->next;
            count--;
        }
        if (count) break; // Less than k nodes, do not reverse

        // Reverse k nodes
        ListNode *prev2 = tail, *curr2 = tail->next;
        while (curr2 != curr) {
            ListNode *temp = curr2->next;
            curr2->next = prev2;
            prev2 = curr2;
            curr2 = temp;
        }
        
        // Connect the reversed group with the rest of the list
        prev->next = prev2;
        tail->next = curr;
        prev = tail;
    }

    return dummy.next;
}

// Function to print the linked list
void printLinkedList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating a linked list
    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);

    int k = 2;
    head = reverseKGroup(head, k);
    printLinkedList(head); // Expected output for k=2: 2 -> 1 -> 4 -> 3 -> 5 -> nullptr
    return 0;
}

Output:

2 -> 1 -> 4 -> 3 -> 5 -> nullptr

Explanation:

The reverseKGroup function reverses nodes in groups of k. It uses a dummy node for simplicity and two pointers, prev and curr, to manage groups. 

For each group, it first checks if there are k nodes available. If yes, it reverses the group of k nodes, then reconnects the reversed group with the rest of the list. 

The process continues until all possible groups are reversed. 

The function returns the modified list with nodes reversed in k-groups, leaving any remaining nodes as they are if they're less than k.