Linked List: Rotate a Doubly Linked list in group of Given Size

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