Last Updated on March 9, 2022 by Ria Pathak

### Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

### Problem Statement

In this problem, we are given a Doubly Linked List and an integer **X**. We are asked to reverse the list in groups of size **X**.

### Problem Statement Understanding

Let’s try to understand the problem statement with the help of examples.

If the given doubly linked list is: 5 1 6 2 7 10 and **X = 3**.

- According to the problem statement, we have been provided a doubly-linked list, and we need to reverse the list in groups of given size i.e. every group of nodes with the size
**X**needs to be reversed. - As we can see in the above given doubly linked list there are two groups 5 1 6 (from index 0 to 2) and 2 7 10 (from index 3 to 5) of size 3 which need to be reversed.
- So after reversing the group of nodes of size 3, our output resultant doubly linked list will be 6 1 5 10 7 2.

Let’s see another example.

If the given doubly linked list is: 5 1 6 2 7 and **X = 3**.

- As we can see in the above given doubly linked list 5 1 6 is a group of nodes of size 3 and 2 7 is a group of size 2. So, we need to reverse these two group of nodes.
- After reversing the above mentioned group of nodes, our resultant doubly linked list will be 6 1 5 7 2

**Note:** Suppose we were asked to reverse every group of nodes of size **X** in a doubly linked list. If in case there remains a group of nodes at the end of the linked list which has size smaller than X, then irrespective of its size we will reverse it in similar way as we were reversing nodes of group of size X.

Now I think from the above examples, the problem is clear. So let’s see how we can approach it.

Before moving to the approach section, try to think about how you can approach this problem.

- If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

### Approach

Our approach will be recursive:

- Here the main idea will be to use recursion to reverse the Doubly Linked List in group of given size, and after reversing a group, we need to call the function again for the next group of nodes if the next node is not null.
- The function will be called recursively until there are no elements left to be reversed.
- After the recursion is over, we will have our doubly linked list reversed in group of given size.

### Algorithm

1) Our recursive function **reverseListInGroupOfX()** will receive the first node of every group of size **X** of the doubly linked list.

2) For every group of nodes in the recursive function **reverseListInGroupOfX()**:

- First, we will reverse the nodes in the current group.
- After the nodes of the current group have been reversed, we will check whether the next group of nodes exists or not:
- If the next group of nodes exists, we will perform the same steps for the next group of nodes that we are performing for the current group.
- Also, for the current group of nodes, we need to link the next and the prev links of a group properly with the next group of nodes and previous group of nodes.

- Finally, we will return the new head of the group.

3) Following all these above steps until all the group of nodes have been reversed, we will get our resultant doubly linked list.

### Dry Run

### Code Implementation

#include<stdio.h> #include<stdlib.h> struct Node { int data; struct Node *next, *prev; }; // function to get a new node struct Node* getNode(int data) { // allocate space struct Node* new_node = (struct Node*)malloc(sizeof(struct 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 beginning // of the Doubly Linked List void push(struct Node** head_ref,struct 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_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 struct Node* revListInGroupOfGivenSize(struct Node* head, int k) { struct Node *current = head; struct Node* next = NULL; struct 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 // pointer to the new head should point to NULL, otherwise you won't be able to traverse list in reverse order using 'prev' newHead->prev = NULL; return newHead; } // Function to print nodes in a // given doubly linked list void printList(struct Node* head) { while (head != NULL) { printf("%d ",head->data); head = head->next; } } // Driver program to test above int main() { // Start with the empty list struct 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; printf("Original list: "); printList(head); // Reverse doubly linked list in groups of // size 'k' head = revListInGroupOfGivenSize(head, k); printf("\nModified list: "); printList(head); return 0; }

#include <bits/stdc++.h> using namespace std; /* Structure of a doubly linked list node */ struct Node { int data; Node *next, *prev; }; /* Creating and returning a new doubly linked list node */ Node* getNewNode(int data) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = data; new_node->next = new_node->prev = NULL; return new_node; } /* Inserting a new node at head of doubly linked list */ void push(Node** newHead, Node* new_node) { new_node->prev = NULL; new_node->next = (*newHead); if ((*newHead) != NULL) (*newHead)->prev = new_node; (*newHead) = new_node; } /* Using this function we will be reversing doubly linked list in group of given size */ Node* reverseListInGroupOfX(Node* head, int X) { Node *current = head; Node* next = NULL; Node* newHead = NULL; int count = 0; while (current != NULL && count < X) { next = current->next; push(&newHead, current); current = next; count++; } if (next != NULL) { head->next = reverseListInGroupOfX(next, X); head->next->prev = head; } return newHead; } /* Using this function we will be printing the linked list content */ void printLinkedList(Node* head) { while (head != NULL) { cout << head->data << " "; head = head->next; } cout<<endl; } int main() { Node* head = NULL; push(&head, getNewNode(10)); push(&head, getNewNode(7)); push(&head, getNewNode(2)); push(&head, getNewNode(6)); push(&head, getNewNode(1)); push(&head, getNewNode(5)); int X = 3; cout<<"Initial doubly linked list"<<endl; printLinkedList(head); head = reverseListInGroupOfX(head, X); cout<<"Doubly linked list after reversing in group of given size"<<endl; printLinkedList(head); return 0; }

class Node { int data; Node next, prev; } class ReverseGroups { static Node getNode(int data) { Node new_node = new Node(); new_node.data = data; new_node.next = new_node.prev = null; return new_node; } static Node push(Node head, Node new_node) { new_node.prev = null; new_node.next = head; if (head != null) head.prev = new_node; head = new_node; return head; } // reversing doubly linked list in group of given size. static Node revListInGroupOfGivenSize(Node head, int k) { Node current = head; Node next = null; Node newHead = null; int count = 0; while (current != null && count < k) { next = current.next; newHead = push(newHead, current); current = next; count++; } if (next != null) { head.next = revListInGroupOfGivenSize(next, k); head.next.prev = head; } return newHead; } static void printLinkedList(Node head) { while (head != null) { System.out.print(head.data + " "); head = head.next; } } public static void main(String args[]) { Node head = null; 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: "); printLinkedList(head); head = revListInGroupOfGivenSize(head, k); System.out.print("\nModified list in groups: "); printLinkedList(head); } }

# Structure of a doubly linked list node class Node: def __init__(self, data): self.data = data self.next = None self.prev = None # Creating and returning a new doubly linked list node def getNode(data): new_node = Node(0) new_node.data = data new_node.next = new_node.prev = None return new_node # Inserting a new node at head of doubly linked list def push(newHead, new_node): new_node.prev = None new_node.next = (newHead) if ((newHead) != None): (newHead).prev = new_node (newHead) = new_node return newHead # Using this function we will be reversing doubly linked list in group of given size def revListInGroupOfGivenSize( head, k): current = head next = None newHead = None count = 0 while (current != None and count < k): next = current.next newHead = push(newHead, current) current = next count = count + 1 if (next != None): head.next = revListInGroupOfGivenSize(next, k) head.next.prev = head return newHead # Using this function we will be printing the linked list content def printList(head): while (head != None): print( head.data , end=" ") head = head.next head = None head = push(head, getNode(10)) head = push(head, getNode(7)) head = push(head, getNode(2)) head = push(head, getNode(6)) head = push(head, getNode(1)) head = push(head, getNode(5)) k = 3 print("Initial doubly linked list") printList(head) head = revListInGroupOfGivenSize(head, k) print("\nDoubly linked list after reversing in group of given size") printList(head)

#### Output

Initial doubly linked list

5 1 6 2 7 10

Doubly linked list after reversing in group of given size

6 1 5 10 7 2

**Time Complexity:** O(n), as we need to traverse the list and traversing takes O(n) time.

[forminator_quiz id=”5116″]

So, In this blog, we have learned how you can reverse a Doubly Linked List in groups of a given size. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.