Problem Statement:
You are given DLL and a number ‘k’.
You need to reverse every group of k nodes in the list
Example
Input: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 k = 2 Output: 2 <-> 1 <-> 4 <-> 3 <-> 6 <-> 5
Solution
We create a recursive function “reverse”, that will reverse the group of ‘k’ nodes
Then it will check if the next group of nodes exists in the list or not.
Then do a recursive call if the next group of nodes exist.
Then return the new head node.
Solution in C++
#include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <unordered_map> #include <vector> #include <stack> using namespace std; struct Node { int data; Node *next; Node *prev; }; Node* getNode(int data) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = data; new_node->next = new_node->prev = NULL; return new_node; } void push(Node** head_ref, Node* new_node) { new_node->prev = NULL; new_node->next = (*head_ref); if ((*head_ref) != NULL) (*head_ref)->prev = new_node; (*head_ref) = new_node; } Node* rev_list_in_group_of_given_size(Node* head, int k) { Node *current = head; Node* next = NULL; Node* newHead = NULL; int count = 0; while (current != NULL && count < k) { next = current->next; push(&newHead, current); current = next; count++; } if (next != NULL) { head->next = rev_list_in_group_of_given_size(next, k); head->next->prev = head; } return newHead; } void printList(Node* head) { while (head != NULL) { cout << head->data << " "; head = head->next; } } int main() { Node* head = NULL; push(&head, getNode(2)); push(&head, getNode(4)); push(&head, getNode(8)); push(&head, getNode(10)); int k = 2; cout << "Original list: "; printList(head); head = rev_list_in_group_of_given_size(head, k); cout << "\nModified list: "; printList(head); return 0; }
Output:
Original list: 10 8 4 2 Modified list: 8 10 2 4