  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Reverse a doubly-linked list in groups of given size

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

// change prev of head node to new node

// move the head to point to the new node
}

// function to reverse a doubly linked list
// in groups of given size
struct Node* revListInGroupOfGivenSize(struct Node* head, int k)
{
struct Node* next = NULL;
int count = 0;

// reversing the current group of k
// or less than k nodes by adding
// them at the beginning of list
while (current != NULL && count < k)
{
next = current->next;
current = next;
count++;
}

// if next group exists then making the desired
if (next != NULL)
{
}

// 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'
}

// Function to print nodes in a
{
}
}

// Driver program to test above
int main()
{

int k = 2;

printf("Original list: ");

// Reverse doubly linked list in groups of
// size 'k'

printf("\nModified list: ");

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 */
{

new_node->prev = NULL;

}

/* Using this function we will be reversing doubly linked list in group of given size */
{
Node* next = NULL;
int count = 0;

while (current != NULL && count < X)
{
next = current->next;
current = next;
count++;
}

if (next != NULL)
{
}
}

/* Using this function we will be printing the linked list content */
{
cout << head->data << " ";
}
cout<<endl;
}

int main()
{

int X = 3;
cout<<"Doubly linked list after reversing in group of given size"<<endl;

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;

}
// reversing doubly linked list in group of given size.
static Node revListInGroupOfGivenSize(Node head, int k)
{
Node next = null;
int count = 0;

while (current != null && count < k)
{
next = current.next;
current = next;
count++;
}
if (next != null)
{
}
}
{
{
}
}
public static void main(String args[])
{

int k = 2;

System.out.print("Original list: ");

System.out.print("\nModified list in groups: ");
}
}
```
```
# 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

new_node.prev = None

# Using this function we will be reversing doubly linked list in group of given size

next = None
count = 0

while (current != None and count < k):

next = current.next
current = next
count = count + 1

if (next != None):

# Using this function we will be printing the linked list content

k = 3

print("\nDoubly linked list after reversing in group of given size")
```