Reversed Linked List In K Groups

#include <bits/stdc++.h> // Common includes
using namespace std;     // Standard namespace

// Node Class: Defines structure of a linked list node
class Node {
public:
    int data;   // Data storage
    Node* next; // Pointer to next node

    // Node Constructor
    Node(int data) {
        this->data = data;
        this->next = NULL; // Initialize next as NULL
    }
};

// printList: Prints all elements in the list
void printList(Node* head) {
    if(head == NULL) {
        cout << "List is Empty!" << endl;
        return;
    }

    cout << "Singly List : ";
    while(head != NULL) {
        cout << head->data << " "; // Print data
        head = head->next;         // Move to next node
    }
    cout << endl;
}

// insertAtHead: Adds node to the beginning
void insertAtHead(Node* &head, int data) {
    Node *temp = new Node(data); // Create new node
    temp->next = head;           // New node points to old head
    head = temp;                 // Head updates to new node
}

// insertAtTail: Adds node to the end
void insertAtTail(Node* &tail, int data) {
    Node *temp = new Node(data); // Create new node
    tail->next = temp;           // Old tail points to new node
    tail = temp;                 // Tail updates to new node
}

// insertAtMiddle: Inserts node at a specific position
void insertAtMiddle(Node* &head, Node* &tail, int data, int pos) {
    if(pos == 1) { // Special case: insert at head
        insertAtHead(head, data);
        return;
    }

    Node *temp = head; // Traverse pointer
    while(temp != NULL && pos > 2) { // Find node BEFORE insertion point
        temp = temp->next;
        pos--;
    }

    if(temp==NULL || pos<=0) { // Invalid position check
        cout << "Invalid Position!" << endl;
        return;
    }

    Node *insertNode = new Node(data); // Create node to insert
    insertNode->next = temp->next;     // New node points to temp's next
    temp->next = insertNode;           // Temp points to new node

    if(insertNode->next == NULL) { // Update tail if inserted at end
        tail = insertNode;
    }
}

// deletePosition: Deletes node at a specific position
void deletePosition(Node* &head, int pos) {
    Node *temp = head; // Pointer for deletion/traversal
    if(pos == 1) {     // Special case: delete head
        head = head->next;
        delete temp;   // Free memory
        return;
    }

    while(temp!=NULL && pos > 2) { // Find node BEFORE deletion point
        temp = temp->next;
        pos--;
    }

    if(temp==NULL || temp->next==NULL || pos<=0) { // Invalid position check
        cout << "Invalid Position!" << endl;
        return;
    }

    Node* target = temp->next; // Node to be deleted
    temp->next = target->next; // Bypass target node
    delete target;             // Free memory
}

// deleteValue: Deletes first occurrence of a specific value
void deleteValue(Node* &head, int val) {
    Node* temp = head->next; // Current pointer
    Node* prev = head;       // Previous pointer

    if(head->data == val) { // Special case: delete head by value
        head = head->next;
        delete prev; // Free old head
        return;
    }

    // Traverse to find the value
    while(temp!=NULL) {
        if(temp->data == val) {
            val = INT_MIN; // Sentinel to mark value found
            break;
        }
        prev = temp;       // Move prev
        temp = temp->next; // Move temp
    }

    if(prev->next==NULL || val!=INT_MIN) { // Value not found
        cout << "Value Not Found!" << endl;
        return;
    }

    prev->next = temp->next; // Bypass target node
    delete temp;             // Free memory
}

// reverseInGroup: Reverses the list in groups of 'k' nodes (Recursive)
Node* reverseInGroup(Node* head, int k) {
    if(head == NULL) { // Base case: empty list
        return head;
    }

    // STEP 1: Reverse K Nodes (Iterative within current group)
    Node* next = NULL; // To store next node after current
    Node* curr = head; // Current node
    Node* prev = NULL; // Previous node (for reversal)
    int count = 0;     // Counter for current group

    while(curr!=NULL && count<k) {
        next = curr->next;  // Save next
        curr->next = prev;  // Reverse current node's pointer

        prev = curr;        // Move prev forward
        curr = next;        // Move curr forward

        count++;            // Increment count
    }

    // STEP 2: Recursive call for remaining list
    if(next != NULL) {
        // Original head (now tail of reversed group) points to reversed next group
        head->next = reverseInGroup(next, k);
    }

    // STEP 3: Return new head of this reversed group
    return prev;
}

// main: Program entry point, demonstrates operations
int main() {
    Node *head = new Node(1); // Create initial node
    Node *tail = head;        // Tail points to head initially

    // Build list: 1 -> 2 -> 4 -> 8 -> 16 -> 32
    for(int i=1; i<=5; i++) {
        insertAtTail(tail, pow(2,i));
    }
    printList(head); // Print original list

    // Reverse in groups of 2
    head = reverseInGroup(head, 2);
    printList(head); // Print list after reversal

    return 0; // Indicate success
}