Reverse a doubly linked list in groups of given size

Given a doubly linked list containing n nodes. The problem is to reverse every group of k nodes in the list.

Examples:

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Prerequisite: Reverse a doubly linked list | Set-2.

Approach: Create a recursive function say reverse(head, k). This function receives the head or the first node of each group of k nodes. It reverses those group of k nodes by applying the approach discussed in Reverse a doubly linked list | Set-2. After reversing the group of k nodes the function checks whether next group of nodes exists in the list or not. If group exists then it makes a recursive call to itself with the first node of the next group and makes the necessary adjustments with the next and previous links of that group. Finally it returns the new head node of the reversed group.

C++

 `// C++ implementation to reverse a doubly linked list ` `// in groups of given size ` `#include ` `  `  `using` `namespace` `std; ` `  `  `// a node of the doubly linked list ` `struct` `Node { ` `    ``int` `data; ` `    ``Node *next, *prev; ` `}; ` `  `  `// function to get a new node ` `Node* getNode(``int` `data) ` `{ ` `    ``// allocate space ` `    ``Node* new_node = (Node*)``malloc``(``sizeof``(Node)); ` `  `  `    ``// put in the data ` `    ``new_node->data = data; ` `    ``new_node->next = new_node->prev = NULL; ` `    ``return` `new_node; ` `} ` `  `  `// function to insert a node at the beginging ` `// of the Doubly Linked List ` `void` `push(Node** head_ref, Node* new_node) ` `{ ` `    ``// since we are adding at the begining, ` `    ``// prev is always NULL ` `    ``new_node->prev = NULL; ` `  `  `    ``// link the old list off the new node ` `    ``new_node->next = (*head_ref); ` `  `  `    ``// change prev of head node to new node ` `    ``if` `((*head_ref) != NULL) ` `        ``(*head_ref)->prev = new_node; ` `  `  `    ``// move the head to point to the new node ` `    ``(*head_ref) = new_node; ` `} ` ` `  `// function to reverse a doubly linked list ` `// in groups of given size ` `Node* revListInGroupOfGivenSize(Node* head, ``int` `k) ` `{ ` `    ``Node *current = head; ` `    ``Node* next = NULL; ` `    ``Node* newHead = NULL; ` `    ``int` `count = 0; ` `     `  `    ``// reversing the current group of k  ` `    ``// or less than k nodes by adding ` `    ``// them at the beginning of list ` `    ``// 'newHead' ` `    ``while` `(current != NULL && count < k) ` `    ``{ ` `        ``next = current->next; ` `        ``push(&newHead, current); ` `        ``current = next; ` `        ``count++; ` `    ``} ` `     `  `    ``// if next group exists then making the desired ` `    ``// adjustments in the link ` `    ``if` `(next != NULL) ` `    ``{ ` `        ``head->next = revListInGroupOfGivenSize(next, k); ` `        ``head->next->prev = head; ` `    ``} ` `     `  `    ``// pointer to the new head of the  ` `    ``// reversed group ` `    ``return` `newHead; ` `} ` ` `  `// Function to print nodes in a ` `// given doubly linked list ` `void` `printList(Node* head) ` `{ ` `    ``while` `(head != NULL) { ` `        ``cout << head->data << ``" "``; ` `        ``head = head->next; ` `    ``} ` `} ` `  `  `// Driver program to test above ` `int` `main() ` `{ ` `    ``// Start with the empty list ` `    ``Node* head = NULL; ` `  `  `    ``// Create doubly linked: 10<->8<->4<->2  ` `    ``push(&head, getNode(2)); ` `    ``push(&head, getNode(4)); ` `    ``push(&head, getNode(8)); ` `    ``push(&head, getNode(10)); ` `     `  `    ``int` `k = 2; ` `  `  `    ``cout << ``"Original list: "``; ` `    ``printList(head); ` `  `  `    ``// Reverse doubly linked list in groups of  ` `    ``// size 'k' ` `    ``head = revListInGroupOfGivenSize(head, k); ` `  `  `    ``cout << ````" Modified list: "````; ` `    ``printList(head); ` `  `  `    ``return` `0; ` `} `

Java

 `// Java implementation to reverse a doubly linked list  ` `// in groups of given size  ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `// Represents a node of doubly linked list ` `class` `Node ` `{ ` `    ``int` `data; ` `    ``Node next, prev; ` `} ` ` `  `class` `GFG  ` `{ ` ` `  `    ``// function to get a new node ` `    ``static` `Node getNode(``int` `data) ` `    ``{ ` `        ``// allocating node ` `        ``Node new_node = ``new` `Node(); ` `        ``new_node.data = data; ` `        ``new_node.next = new_node.prev = ``null``; ` ` `  `        ``return` `new_node; ` `    ``} ` ` `  `    ``// function to insert a node at the beginning  ` `    ``// of the Doubly Linked List  ` `    ``static` `Node push(Node head, Node new_node)  ` `    ``{ ` `        ``// since we are adding at the beginning,  ` `        ``// prev is always NULL  ` `        ``new_node.prev = ``null``; ` ` `  `        ``// link the old list off the new node ` `        ``new_node.next = head; ` ` `  `        ``// change prev of head node to new node  ` `        ``if` `(head != ``null``) ` `            ``head.prev = new_node; ` ` `  `        ``// move the head to point to the new node  ` `        ``head = new_node; ` `        ``return` `head; ` `    ``} ` ` `  `    ``// function to reverse a doubly linked list  ` `    ``// in groups of given size  ` `    ``static` `Node revListInGroupOfGivenSize(Node head, ``int` `k) ` `    ``{ ` `        ``Node current = head; ` `        ``Node next = ``null``; ` `        ``Node newHead = ``null``; ` `        ``int` `count = ``0``; ` ` `  `        ``// reversing the current group of k  ` `        ``// or less than k nodes by adding  ` `        ``// them at the beginning of list  ` `        ``// 'newHead' ` `        ``while` `(current != ``null` `&& count < k) ` `        ``{ ` `            ``next = current.next; ` `            ``newHead = push(newHead, current); ` `            ``current = next; ` `            ``count++; ` `        ``} ` ` `  `        ``// if next group exists then making the desired  ` `        ``// adjustments in the link  ` `        ``if` `(next != ``null``) ` `        ``{ ` `            ``head.next = revListInGroupOfGivenSize(next, k);  ` `            ``head.next.prev = head; ` `        ``} ` ` `  `        ``// pointer to the new head of the  ` `        ``// reversed group ` `        ``return` `newHead;  ` `    ``} ` ` `  `    ``// Function to print nodes in a  ` `    ``// given doubly linked list  ` `    ``static` `void` `printList(Node head) ` `    ``{ ` `        ``while` `(head != ``null``) ` `        ``{ ` `            ``System.out.print(head.data + ``" "``); ` `            ``head = head.next; ` `        ``} ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``// Start with the empty list ` `        ``Node head = ``null``;  ` `             `  `        ``// Create doubly linked: 10<->8<->4<->2 ` `        ``head = push(head, getNode(``2``)); ` `        ``head = push(head, getNode(``4``)); ` `        ``head = push(head, getNode(``8``)); ` `        ``head = push(head, getNode(``10``)); ` ` `  `        ``int` `k = ``2``; ` `             `  `        ``System.out.print(``"Original list: "``); ` `        ``printList(head); ` ` `  `        ``// Reverse doubly linked list in groups of  ` `        ``// size 'k' ` `        ``head = revListInGroupOfGivenSize(head, k);  ` ` `  `        ``System.out.print(````" Modified list: "````); ` `        ``printList(head); ` `    ``} ` `} ` ` `  `// This code is contributed by rachana soma `

C#

 `// C# implementation to reverse a doubly linked list  ` `// in groups of given size  ` `using` `System; ` ` `  `// Represents a node of doubly linked list  ` `public` `class` `Node  ` `{  ` `    ``public` `int` `data;  ` `    ``public` `Node next, prev;  ` `}  ` ` `  `class` `GFG  ` `{  ` ` `  `    ``// function to get a new node  ` `    ``static` `Node getNode(``int` `data)  ` `    ``{  ` `        ``// allocating node  ` `        ``Node new_node = ``new` `Node();  ` `        ``new_node.data = data;  ` `        ``new_node.next = new_node.prev = ``null``;  ` ` `  `        ``return` `new_node;  ` `    ``}  ` ` `  `    ``// function to insert a node at the beginning  ` `    ``// of the Doubly Linked List  ` `    ``static` `Node push(Node head, Node new_node)  ` `    ``{  ` `        ``// since we are adding at the beginning,  ` `        ``// prev is always NULL  ` `        ``new_node.prev = ``null``;  ` ` `  `        ``// link the old list off the new node  ` `        ``new_node.next = head;  ` ` `  `        ``// change prev of head node to new node  ` `        ``if` `(head != ``null``)  ` `            ``head.prev = new_node;  ` ` `  `        ``// move the head to point to the new node  ` `        ``head = new_node;  ` `        ``return` `head;  ` `    ``}  ` ` `  `    ``// function to reverse a doubly linked list  ` `    ``// in groups of given size  ` `    ``static` `Node revListInGroupOfGivenSize(Node head, ``int` `k)  ` `    ``{  ` `        ``Node current = head;  ` `        ``Node next = ``null``;  ` `        ``Node newHead = ``null``;  ` `        ``int` `count = 0;  ` ` `  `        ``// reversing the current group of k  ` `        ``// or less than k nodes by adding  ` `        ``// them at the beginning of list  ` `        ``// 'newHead'  ` `        ``while` `(current != ``null` `&& count < k)  ` `        ``{  ` `            ``next = current.next;  ` `            ``newHead = push(newHead, current);  ` `            ``current = next;  ` `            ``count++;  ` `        ``}  ` ` `  `        ``// if next group exists then making the desired  ` `        ``// adjustments in the link  ` `        ``if` `(next != ``null``)  ` `        ``{  ` `            ``head.next = revListInGroupOfGivenSize(next, k);  ` `            ``head.next.prev = head;  ` `        ``}  ` ` `  `        ``// pointer to the new head of the  ` `        ``// reversed group  ` `        ``return` `newHead;  ` `    ``}  ` ` `  `    ``// Function to print nodes in a  ` `    ``// given doubly linked list  ` `    ``static` `void` `printList(Node head)  ` `    ``{  ` `        ``while` `(head != ``null``)  ` `        ``{  ` `            ``Console.Write(head.data + ``" "``);  ` `            ``head = head.next;  ` `        ``}  ` `    ``}  ` ` `  `    ``// Driver code  ` `    ``public` `static` `void` `Main(String []args)  ` `    ``{  ` `        ``// Start with the empty list  ` `        ``Node head = ``null``;  ` `             `  `        ``// Create doubly linked: 10<->8<->4<->2  ` `        ``head = push(head, getNode(2));  ` `        ``head = push(head, getNode(4));  ` `        ``head = push(head, getNode(8));  ` `        ``head = push(head, getNode(10));  ` ` `  `        ``int` `k = 2;  ` `             `  `        ``Console.Write(``"Original list: "``);  ` `        ``printList(head);  ` ` `  `        ``// Reverse doubly linked list in groups of  ` `        ``// size 'k'  ` `        ``head = revListInGroupOfGivenSize(head, k);  ` ` `  `        ``Console.Write(````" Modified list: "````);  ` `        ``printList(head);  ` `    ``}  ` `}  ` ` `  `// This code is contributed by Arnab Kundu `

Output:

```Original list: 10 8 4 2
Modified list: 8 10 2 4
```

Time Complexity: O(n).